オートマトン L = {ww^R: w ∈ {a, b}+}の中心の見つけ方

質問

下記のようなオートマトンがあります。

L = {ww^R: w ∈ {a, b}+}
M = (Q, Σ, Γ, δ, q0, z, F)
Q = (q0, q1, q2),
Σ = {a, b},
Γ = {a, b, z},
F = {q2}.

(1)wをスタックに載せるために:
δ(q0, a, a) = {(q0, aa)}
δ(q0, b, a) = {(q0, ba)}
δ(q0, a, b) = {(q0, ab)}
δ(q0, b, b) = {(q0, bb)}
δ(q0, a, z) = {(q0, az)}
δ(q0, b, z) = {(q0, bz)}

(2)どこが文の中心か見つけるために(状態がq0からq1に変わる):
δ(q0, λ, a) = {(q1, a)}
δ(q0, λ, b) = {(q1, b)}

(3)w^Rと一致させるために:
δ(q1, a, a) = {(q1, λ)}
δ(q1, b, b) = {(q1, λ)}

(4)最後に:
δ(q1, λ, z) = {(q2, z)}

とあります。
問題の中にこれを元にしてL = {wcw^R: w ∈ {a, b}*}のnpdaをつくりなさい、
というのがありますが、それは(2)を
δ(q0, c, a) = {(q1, a)} ←cが入力されたらそこが中心
δ(q0, c, b) = {(q1, b)}
に変えて
δ(q0, λ, z) = {(q2, λ)} ←何も入力されなかったら文字を受け付ける(* → +なので)
を付け加えればよいですか? (多分、そうですよね?)

それと、上の(2)がどうやって中心を見つけているのか分かりません。
入力中は何文字入力されるかなんて分かりませんよね。
例えばbaabbaabという文があったとすると最初の四文字でbaabで
「さては中心はbaとabの間だな!」とか勘違いとかしないんですか?
入力がλということは毎回毎回入力がある度にチェックしているということでしょうか?
混乱している私に分かりやすい説明ができる方、どうかお願いします。

回答No.1

hpsk · ベストアンサー

先の2つの御質問からすると、non-deterministic（非決定的）なPDAを考えているわけですよね。

非決定的なオートマトンでは、「１つの入力系列に対して複数の遷移経路が考えられるが、そのうち１つでも受理状態で遷移が終了する経路が存在すれば、オートマトンはその入力を受理する」と考えます。

baabbaabの例であれば、"b"しか入力されていない状態、"ba"まで入力された状態、...、"baabbaab"まで入力されてしまった状態、のどこで(2)の遷移をやってもいいんです。
そのうち"baab"の状態で(2)の遷移をすれば受理状態で遷移が終了するので、このオートマトンは"baabbaab"を受理するといえるわけです。

> それは(2)を
> ....
> を付け加えればよいですか? (多分、そうですよね?)
そこはそれで合っていると思いますよ。

お礼

ああ! ではnfaとまったく同じ考え方なんですね。
non-deterministic（非決定的）というのはそういうことなんですね。
ということは、
スタックが'z'になって後はλの入力さえあれば受理、という状態もある一方で、
今まで入力された文の逆文の入力待ちになっている状態も同時に存在する、ということですね。
理解できました。
これからももっともっと勉強してみます。
本当にありがとうございました!