pushdown-automaton - 要素が異なるプッシュダウン オートメーション

Question

L = {0,1}^* という言語があり、1 と 0 は同じ数ではないはずです。それをPDAオートマトンでどのように表現できますか？

前もって感謝します！

Answer 1

PDA は、入力を読み取り、スタックにプッシュし、スタックからポップすることができます。オートマトン、特に PDA や TM を設計しようとするとき、私は入力文字列をテーブルに並べられた色付きのビー玉またはチップの長い列と考えるのが好きです。問題は、スタックを 1 つだけ使用し、左から右にチップを拾って、チップの列に赤と青のチップの数が異なるかどうかをどのように判断できるかということです。

1 つの方法は次のとおりです。ビー玉を拾うときは、スタックを見てください。スタックが空の場合、または同じ色のチップが上にある場合は、チップを下に置きます。一番上のチップの色が違う場合は、拾ったチップとスタックの一番上のチップを袋に入れます。すべてのチップを拾うまで続けます。次に、スタックを見てください。スタックが空の場合、同じ数の赤チップと青チップを捨てたに違いありません。スタックにいくつかのチップがある場合、それは捨てることができなかったチップがあったことを意味します。実際、残ったチップの色によって、どのチップが多かったかがわかります。