PDA を使用して CFG またはタイプ 2 グラマーの遷移を定義する際に、Zo で示される初期スタック シンボルが必要です。私の疑問は、最終的にスタックをまったく空にするので、なぜそれが必要なのかということです....??
1 に答える
2
各移動は現在の入力シンボルとスタックの一番上にあるシンボルによって決定されるため、プッシュダウン オートマトンには初期スタック シンボルが必要です。これにより、スタックが空の場合は移動できないという現実が生じます。
はい、スタックはスタックシンボルのみに減らすことができます。検討...
L={ (a^n)(b^n) : n >= 0 }
0読んだそれぞれに対してa を押し下げることができましたがa、これは-ところで-最初のものは (q0、a、z) になり、最初に読んだときにsbをポップ0して何も押し戻しません。入力が消費されず、スタック シンボルがスタックの一番上にある場合、言語は受け入れられます。
上記の遷移関数では、最初の動きが最初の入力とスタック シンボルによって決定されることに注意してください。それなしでは始められないことがわかりますか？
于 2015-04-10T18:55:00.670 に答える