computer-science - 言語 A = {0^n 1^n 0^n} は文脈自由ですか?

Question

私はちょうど別の言語にいくつかの考えを入れていました（最終試験が近づいているので見直しています）、言語を処理するための有効なプッシュダウンオートマトンを考えることができません A = {0^n 1^n 0^n | n >= 0}。これは文脈自由言語ではありませんよね？

Answer 1

私はあなたがいると信じています。言語L = { a^ib^ic^i | i > 0 }は、ポンピング補題に関するウィキペディアの記事で、言語が文脈自由でないことを証明する方法の例として使用されています。

Answer 2

ちょっとだけ{0^n 1^n}の部分を考えてみてください。とを置き換える0と、単純なネストされた括弧の言語が得られます。これは、言語が規則的ではないという完全な景品です。(1)

最後の0^nを追加すると、状況依存になります（つまり、状況自由ではありません）。CFGは、唯一のデータ構造として単一のスタックを持つ有限状態コンピューターによって決定できることに注意してください。0を見るとキャラクターがスタックにプッシュされ、1を見るとスタックからポップします。これにより、1と同じ数の0が存在することが保証されますが、それ以上の0を一致させる方法はありません。