0

このオートマトンの遷移関数を構築するのに行き詰まっています。

aごとに1をスタックし、bごとにアンスタックする必要があると思います

c の数は ab ペアの数に等しいので、遭遇する b ごとに 0 をスタックする必要があると思います。問題は、1 のスタックを解除して 0 を同時に追加するにはどうすればよいかということです。

4

1 に答える 1

5

0に遭遇するたびに をスタックにプッシュしないでくださいb。代わりに、 a0に遭遇するたびに a をスタックにプッシュしb、スタックが空であるか、スタックの一番上が a であるようにします0。

したがって、命名法を次のように使用しますaabbabcc。

read a push 1
read a push 1
read b pop 1
read b pop 1
stack is empty so push 0
read a push 1
read b pop 1 
top of stack is 0 so push 0
read c pop 0
read c pop 0

スタックは空なので、この文字列を受け入れます。

于 2010-01-17T20:21:38.600 に答える