オートマトン: npdaとdpdaの違い

質問

L={a^n b^n: n>=0}をnpdaで表すとこうでした:

F={q2}

δ(q0, λ, z) = {(q2, z)} ←文字列がλ(空)だった場合

δ(q0, a, z) = {(q0, 1z)}
δ(q0, a, 1) = {(q0, 11)}
δ(q0, b, 1) = {(q1, λ)}
δ(q1, b, 1) = {(q1, λ)}
δ(q1, λ, z) = {(q2, z)}

しかし、dpdaではこうです:

F={q0}

δ(q0, a, z) = {(q1, 1z)}
δ(q1, a, 1) = {(q1, 11)}
δ(q1, b, 1) = {(q2, λ)}
δ(q2, b, 1) = {(q2, λ)}
δ(q2, λ, z) = {(q0, λ)}

明らかな違いとして
npdaではδ(q0, a, z)とδ(q0, a, 1)の両方があるので
状態q0に対してaが入力されても
スタックの一番上がzの場合と1の場合の2つの選択肢があります。
dpdaではそれを避けるためにδ(q0, a, z)の後で状態をq1に進めています。
これで状態q0でaが入力された場合は選択肢は一つになります。
(これがnpdaとdpdaの定義ですよね…って自信ないんですが)

さて、ここで質問です。
(1)なぜdpdaでは文字列がλ(空)だった場合がないのでしょうか?
これだと文字列がλ(空)だった場合、受理されないと思うんですがどうでしょうか?

(2)dpdaではなぜδ(q2, λ, z) = {(q0, λ)}のようにq0が最終状態なんでしょうか?
q3で終わらせても問題ないと思うんですけどどうでしょうか?

(3)しかも最終状態は{(q0, z)}ではなく{(q0, λ)}なのはなぜでしょうか?
誰かが「{(q0, z)}ではababも受理されてしまうから」と言ってたような気がしますが
本当かどうか分かりません。

この通り、完全に理解できていません。どうかお助けください。お願いします。

回答No.2

hpsk · ベストアンサー

> これで状態q0でaが入力された場合は選択肢は一つになります。
と、
> スタックも含めた状態と入力によって、その後の状態が一通りに決まるものが
> 確定的オートマトン、そうでないものが非確定的オートマトン
どちらも基本的には同じ事を言っていると思いますが、、、（つまりどちらも合っている）

前者のpdaは間違いなく非決定的です。
スタックが空で入力がaのときに素直に入力を消費するか、入力を消費せずに遷移するか（ε遷移）の２種類の遷移が選択できるからです。

それを踏まえて、

（１）
文字列が空の場合、全く遷移が行われません。
しかし、初期状態＝受理状態なので、それでもちゃんと受理してくれます。

（２）
#1の方の
> が、後者は間違いではないかと思います。
にも関係しますが、dpdaの場合の
δ(q2, λ, z) = {(q0, λ)}
は、「入力がもう終わりなら遷移する」と解釈するのが妥当ではないかと思います。そう読めば間違いではありません。
そもそも、「入力を消費せずに遷移」の意味のε遷移は、それが存在しただけで非決定的になりますので。

そう思うと、（２）は、
入力が空の場合にはq3に遷移して、δ(q2, λ, z) = {(q0, λ)}の遷移先をq3に変え、q3を受理状態にしてもかまわないけれど、無駄に状態数と遷移規則を増やすだけなのでしていない。
という回答になります。

（３）
まず、「最終状態が{(q0, z)}」という言い方はヘンですね。
スタックをpopしてzをpushし、q0に遷移する操作を定義しているだけですので。

pdaの定義が「入力を全て消費して、受理状態に達しており、『スタックが空』なら受理とみなす」
というものなら、最後は{(q0, λ)}でなければなりません。そうでないと、スタックに"z"というゴミが残ってしまい、受理になりませんので。
一方、入力を消化した時点で受理状態ならばよい、というpdaの定義の仕方も存在して、その場合はどちらでもよいです。

お礼

お礼が遅くなってしまって申し訳ありません。

>（１）
>文字列が空の場合、全く遷移が行われません。
>しかし、初期状態＝受理状態なので、それでもちゃんと受理してくれます。

なるほど! 遷移が行われなくてもq0がファイナルなので受理できるんですね。
今思い出しましたが、dfaで文字列λを受理するにはq0をファイナルにする以外方法がないんでしたね。

> （２）は、
> 入力が空の場合にはq3に遷移して、δ(q2, λ, z) = {(q0, λ)}の遷移先をq3に変え、q3を受理状態にしてもかまわないけれど、無駄に状態数と遷移規則を増やすだけなのでしていない。

（１）の状態で受理されるのが分かったのでこれも理解できます。

> 「最終状態が{(q0, z)}」という言い方はヘンですね。

ただの操作でした…。(^^ゞ

> （３）
> pdaの定義が「入力を全て消費して、受理状態に達しており、『スタックが空』なら受理とみなす」
> というものなら、最後は{(q0, λ)}でなければなりません。そうでないと、スタックに"z"というゴミが残ってしまい、受理になりませんので。
> 一方、入力を消化した時点で受理状態ならばよい、というpdaの定義の仕方も存在して、その場合はどちらでもよいです。

定義が二つあるんですね。多分、うちは前者だと思います。
これもまた（１）が関係してるんですね。

こんな私でも理解できました。本当にありがとうございました!

回答No.1

ranx

> これがnpdaとdpdaの定義ですよね
違うと思います。スタックも含めた状態と入力によって、
その後の状態が一通りに決まるものが確定的オートマトン、
そうでないものが非確定的オートマトンのはずです。
挙げられた例は、いずれも確定的オートマトンだと思います。

が、後者は間違いではないかと思います。
aabbaabb
のような入力も受理してしまいそうに思うのですが、いかがですか？

お礼

もしかして後者(dpda)の最後の行の

δ(q2, λ, z) = {(q0, λ)}

の操作によって一行目の

δ(q0, a, z) = {(q1, 1z)}

にまた戻ってしまう →永久にループが可能、と勘違いされていたのではないでしょうか。
実は私もそう思っていたんですよ。
しかし、最後の行の操作は{(q0, z)}ではなく{(q0, λ)}なので

δ(q0, a, λ) = {(q1, 1z)}

などという新しい行でもない限り、ループすることはないでしょう。
…と言いたいところですが、dpdaなので
状態がq0、入力がaに対してzとλの二つの選択肢があってはなりませんね、きっと。
ということで、もし後者(dpda)に

δ(q2, a, z) = {(q1, 1z)}

という記述があったならaabbaabbやaabbaabbaabbやaabbaabbaabbaabbなども受理できたのでは、と思います。
(むちゃくちゃ自信ないですけど (^^ゞ)
早くこれらの知識をコンピューター上で試してみたいです。
ありがとうございました!