1

私の講義では、{(a^n)(b^n): n is greater than or equal to zero} という言語を受け入れるプッシュダウン オートマトンの例が示されています。

Q - set of states ={s,p,f}
L - alphabet = {a,b}
R - stack = {a}
F - accepting states ={s,f}
D -transition relation ={
(s,a,e),(p,a)
(p,a,e),(p,a)
(p,b,a),(f,e)}

私の質問は、なぜ状態 p と f が必要なのですか? 状態 s を使用することはできませんか?

また、PDAを構築するときに、必要な状態の数とスタックのアルファベットを知る方法はありますか? それとも直感で解けばいいのでしょうか?

4

1 に答える 1

0

状態 p を持たない場合、PDA は同じ数の a と b を持つ任意の文字列を受け入れます。

非形式的な記述を形式的な記述に変換するので、状態または遷移の数を事前に知るための非直感的な方法はありません。形式的な方法はありません!

于 2015-12-08T05:20:02.920 に答える