通常の言語のセットがコンテキストフリー言語のセットの適切なサブセットであることを証明します

Question

私はいくつかの計算理論で（宿題ではなく）ブラッシュアップしていましたが、この問題を抱えていました。

通常の言語のセットがコンテキストフリー言語のセットの適切なサブセットであることをどのように証明できますか。

今、私は言語が定期的である場合、有限のオートマトンによって受け入れられている場合です。

そして、私は言語がプッシュダウンオートマトンによって受け入れられている場合、コンテキストフリーであることを知っています。

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

Answer 1

DFAは、たまたまスタックに何もプッシュしないPDAに相当するため、すべての通常の言語もコンテキストがありません。もっと正式に：

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

PDAは、DFAのすべての要素に加えて、γ（スタックアルファベット）とZ（初期スタックシンボル）の2つの追加パラメーターを含む7タプルとして定義されます。 PDA遷移テーブルは、DFA遷移テーブルとは多少異なります。各遷移は、入力記号と電流スタック記号の両方に依存し、遷移がスタックからプッシュまたはポップする場合があります。

したがって、単一のシンボルで構成されるダミースタックアルファベットを導入することにより、DFA遷移テーブルをマッピングするのは些細なことです（やや迷惑で長い間書き留めます！）(state, input) -> state 同等のPDA遷移テーブルへ (state, input, stack) -> (state, stack).

適切なサブセット関係の証明を完了するには：コンテキストがないが通常ではない言語が存在するため、通常の言語はコンテキストのない言語の適切なサブセットを形成します。例：バランスの取れた括弧で構成される文字列の言語。