オートマトン npda(=non-deterministic pushdown automata)について

質問

オートマトン npda(=non-deterministic pushdown automata)について質問です。
npdaを勉強しているのですが例題が少なすぎて理解できていません。
本ではL={a^n b^n: n>=0}ではnpdaは

δ(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)}

ということです。問題はL={a^n b^2n: n>=0}のnpdaです。
bがaの二倍ということなのでaが入力されたときに
スタックに二つ積めばいいのでは、と解釈して

δ(q0, λ, z) = {(q2, z)}
δ(q0, a, z) = {(q0, 1z)}
δ(q0, a, 1) = {(q0, 111)} ←ここだけ変えました
δ(q0, b, 1) = {(q1, λ)}
δ(q1, b, 1) = {(q2, λ)}
δ(q1, λ, z) = {(q1, z)}

で良いでしょうか?

回答No.1

hpsk · ベストアンサー

考え方はそれでいいと思います。
ただし、
> δ(q0, a, z) = {(q0, 1z)}
も
δ(q0, a, z) = {(q0, 11z)}
とする必要がありますね。

お礼

回答をいただいたお陰でようやくnpdaの動きが理解できるようになりました。
最初のaの入力でも同じように1増やしてあげなければならなかったんですね。
ありがとうございました!