language-theory - 正規言語のセットが文脈自由言語のセットの適切なサブセットであることを証明する

Question

私はいくつかの計算理論について（宿題ではなく）ブラッシュアップしていて、この問題に遭遇しました：

通常の言語のセットが文脈自由言語のセットの適切なサブセットであることをどのように証明できますか。

これで、言語が有限オートマトンによって受け入れられれば、その言語は規則的であることがわかりました。

また、プッシュダウン オートマトンによって受け入れられる言語は文脈自由であることも知っています。

しかし、私は解決策が何であるかわかりません。

Answer 1

DFA は、たまたまスタックに何もプッシュしない PDA と同等です。したがって、すべての通常の言語もコンテキストフリーです。より正式には：

DFA は、入力アルファベット、状態のセット、開始状態、遷移テーブル、および最終 (受け入れ) 状態のセットで構成される 5 タプル (Σ、S、s0、δ、F) として定義されます。

PDA は、DFA のすべての要素に加えて、Γ (スタック アルファベット) と Z (初期スタック シンボル) の 2 つの追加パラメーターを含む 7 タプルとして定義されます。PDA トランジション テーブルは、DFA トランジション テーブルとは多少異なります。各トランジションは、入力シンボルと現在のスタック シンボルの両方に依存することができ、トランジションはスタックからプッシュまたはポップすることができます。

(state, input) -> stateしたがって、単一のシンボルで構成されるダミーのスタック アルファベットを導入することで、DFA 遷移表を同等の PDA 遷移表にマッピングするのは簡単です (ただし、書き出すのは面倒で時間がかかります) (state, input, stack) -> (state, stack)。

適切な部分集合関係の証明を完成させるために: 文脈自由であるが規則的ではない言語が存在するため、規則的な言語は文脈自由言語の適切な部分集合を形成します。例: バランスの取れた括弧で構成される文字列の言語。