二つのよく似たオートマトン
本に二つのよく似たオートマトン npda(=non-deterministic pushdown automaton)があります。
片方はΓ={0, 1}ですがもう片方はΓ={z, 1}です。
(1)npda for {a^n b^n: n>=0} ∪ {a}
Q = {q0, q1, q2, q3}
Σ = {a, b}
Γ = {0, 1} ←大きな違い
z = 0
F = {q3}
q0: 'a's coming in ??? 自信なし
q1: 'b's coming in ??? 自信なし …というか分かりません。
q2: 'b's going out ??? 自信なし
q3: final state
δ(q0, a, 0) = {(q1, 10), (q3, λ)} ←これは{a}の部分なので消せば(2)と同じになるはず
δ(q0, λ, 0) = {(q3, λ)}
δ(q1, a, 1) = {(q1, 11)}
δ(q1, b, 1) = {(q2, λ)}
δ(q2, b, 1) = {(q2, λ)}
δ(q2, λ, 0) = {(q3, λ)}
(2)npda for {a^n b^n: n>=0}
Q = {q0, q1, q2}
Σ = {a, b}
Γ = {z, 1} ←大きな違い
z = 無記入
F = {q2}
q0: 'a's coming in
q1: 'b's coming in
q2: final state
δ(q0, λ, z) = {(q2, z)}
δ(q0, a, z) = {(q0, 1z)}
δ(q0, a, 1) = {(q0, 11)}
δ(q0, b, 1) = {(q1, λ)}
δ(q1, b, 1) = {(q2, λ)}
δ(q1, λ, z) = {(q1, z)}
Γの"0"が"z"に入れ替わっただけかと思ったのですが
ステート(=state, q0やらq1やら)の数も違いますし、入力の仕方も違います。
質問1. {a}の部分を除けば両者とも{a^n b^n: n>=0}になりますか?
質問2. もしそうであるならば、なぜΓを{0, 1}と{z, 1}などと変えているのですか? それはstatesの数に関係ありますか?
![その他([技術者向] コンピューター) イメージ](https://gazo.okwave.jp/okwave/images/related_qa/c205_3_thumbnail_img_sm.png)
