文脈自由文法の場合、どのようにそれを同等のプッシュダウンオートマトンに変換するのですか？

Question

開始変数Sを持つ文脈自由文法GがΣ= {0,1,2}である場合：
S→0S0 | 1S1 | 2S2 | Y
Y→私はプッシュダウンオートマトンは、スタックの一番上に記号をプッシュし、それらをオフにポップすることができます同等のプッシュダウンオートマトン

Answer 1

にこれを有効にするにはどうすればよい22

。また、最上位のスタックシンボルにトランジションを基にすることもできます。スタックを操作して適切な言語を受け入れる仕組みを考える必要があります。

あなたの文法が生成する言語は、次のような特徴があります

1. 、それは{0, 1, 2}以上の回文で途中
で 22
2. を持っています。つまり、同じ前進を後ろ向きに読む。

文字列の末尾が後方に繰り返されているかどうかを確認できるように、文字列の先頭を「覚えておく」必要があります。これはスタックの良いユースケースです。シンボルを見てスタックにプッシュし、読み返している間にシンボルをポップすることができます。もう1つの注意点：22を読んだ後で読むことができます。

まず、我々はすべてを読んで、私たちは「22」を見つけるまで、スタックにプッシュ：

Q s S Q' S' 
---------------------- 
// read 0s and 1s and push them on the stack 
q0 0 Z q0 0Z 
q0 0 0 q0 00 
q0 0 1 q0 01 
q0 1 Z q0 1Z 
q0 1 0 q0 10 
q0 1 1 q0 11 

// if you read a 2, pus it on the stack and 
// go to a new state where we look for a second 2 
q0 2 Z q1 2Z 
q0 2 0 q1 20 
q0 2 1 q1 21 

// if you read a 2 and then 0 or 1, go back to the 
// initial state and keep reading input. otherwise, 
// if you find a second two, proceed 
q1 0 2 q0 02 
q1 1 2 q0 12 
q1 2 2 q2 22 

// assume the '22' we just saw was not the one in 
// the middle of the input string and that we need 
// to keep reading input. 
q2 0 2 q0 02 
q2 1 2 q0 12 
q2 2 2 q2 22 

// assume the '22' we just saw was the one in the 
// middle of the input string and that we now need 
// to start reading from the stack. 
q2 - 2 q3 - 
q3 - 2 q4 - 
q4 0 0 q4 - 
q4 1 1 q4 - 
q4 2 2 q4 - 
q4 - Z q5 Z 

// we read a string in the language and are 
// ready to accept in q5. go to dead state q6 
// explicitly if still have input. 
q5 0 Z q6 Z 
q5 1 Z q6 Z 
q5 2 Z q6 Z 

// consume the rest of the input in the dead state. 
q6 0 Z q6 Z 
q6 1 Z q6 Z 
q6 2 Z q6 Z 

遷移をq5ために、あなたは、文字列を意味するためにマシンをクラッシュ定義する場合q6は厳密には必要ありませんはっきりと拒否されており、これは典型的なものです。これらの遷移を含めるので、PDAはクラッシュすることなく正常にすべての入力を使い果たします。

このPDAは確定的ではありません。この言語には決定的なPDAはありません。基本的には、部分文字列22を読み取った後、22のインスタンスが中間にあるかどうかを推測する必要があります。もしそうなら、最初の文字列を読み戻して、回文があるかどうかを調べる必要があります。もしそうでなければ、スタック上にシンボルを押し続ける必要があります。