二つのよく似たオートマトン

質問

本に二つのよく似たオートマトン 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の数に関係ありますか?

回答No.1

hpsk · ベストアンサー

Γが{0, 1}から{z, 1}に変わっていることには特に深い意味はないと思います。

{a^n b^n: n>=0} ∪ {a} のオートマトンでstateの種類が１個余計に必要なのは、
・今からaが入力された後、bが同じ数だけ入力されて受理状態に落ち着くかもしれないし、1個だけaが入力されて受理状態に落ち着くかもしれないという状態
と、
・今からaが入力された後、bが同じ数だけ入力されて受理状態に落ち着くという状態（この状態から1個だけaが入力されて受理、というのは許されない）
の２つを区別する必要があるからです。
前者の状態がq0，後者の状態がq1に相当します。

質問1の答はYesになりますが、この場合、q0とq1をわざわざ分ける必要はないわけですね。

お礼

>stateの種類が１個余計に必要なのは…
>２つを区別する必要があるからです。

なるほど、それで理由が分かりました。
説明が本当に上手ですね。まるで絡んだ紐を一つ一つ解いているようです。
ありがとうございました!