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ベストアンサー
- 回答日時:
> これで状態q0でaが入力された場合は選択肢は一つになります。
と、
> スタックも含めた状態と入力によって、その後の状態が一通りに決まるものが
> 確定的オートマトン、そうでないものが非確定的オートマトン
どちらも基本的には同じ事を言っていると思いますが、、、(つまりどちらも合っている)
前者のpdaは間違いなく非決定的です。
スタックが空で入力がaのときに素直に入力を消費するか、入力を消費せずに遷移するか(ε遷移)の2種類の遷移が選択できるからです。
それを踏まえて、
(1)
文字列が空の場合、全く遷移が行われません。
しかし、初期状態=受理状態なので、それでもちゃんと受理してくれます。
(2)
#1の方の
> が、後者は間違いではないかと思います。
にも関係しますが、dpdaの場合の
δ(q2, λ, z) = {(q0, λ)}
は、「入力がもう終わりなら遷移する」と解釈するのが妥当ではないかと思います。そう読めば間違いではありません。
そもそも、「入力を消費せずに遷移」の意味のε遷移は、それが存在しただけで非決定的になりますので。
そう思うと、(2)は、
入力が空の場合にはq3に遷移して、δ(q2, λ, z) = {(q0, λ)}の遷移先をq3に変え、q3を受理状態にしてもかまわないけれど、無駄に状態数と遷移規則を増やすだけなのでしていない。
という回答になります。
(3)
まず、「最終状態が{(q0, z)}」という言い方はヘンですね。
スタックをpopしてzをpushし、q0に遷移する操作を定義しているだけですので。
pdaの定義が「入力を全て消費して、受理状態に達しており、『スタックが空』なら受理とみなす」
というものなら、最後は{(q0, λ)}でなければなりません。そうでないと、スタックに"z"というゴミが残ってしまい、受理になりませんので。
一方、入力を消化した時点で受理状態ならばよい、というpdaの定義の仕方も存在して、その場合はどちらでもよいです。
お礼が遅くなってしまって申し訳ありません。
>(1)
>文字列が空の場合、全く遷移が行われません。
>しかし、初期状態=受理状態なので、それでもちゃんと受理してくれます。
なるほど! 遷移が行われなくてもq0がファイナルなので受理できるんですね。
今思い出しましたが、dfaで文字列λを受理するにはq0をファイナルにする以外方法がないんでしたね。
> (2)は、
> 入力が空の場合にはq3に遷移して、δ(q2, λ, z) = {(q0, λ)}の遷移先をq3に変え、q3を受理状態にしてもかまわないけれど、無駄に状態数と遷移規則を増やすだけなのでしていない。
(1)の状態で受理されるのが分かったのでこれも理解できます。
> 「最終状態が{(q0, z)}」という言い方はヘンですね。
ただの操作でした…。(^^ゞ
> (3)
> pdaの定義が「入力を全て消費して、受理状態に達しており、『スタックが空』なら受理とみなす」
> というものなら、最後は{(q0, λ)}でなければなりません。そうでないと、スタックに"z"というゴミが残ってしまい、受理になりませんので。
> 一方、入力を消化した時点で受理状態ならばよい、というpdaの定義の仕方も存在して、その場合はどちらでもよいです。
定義が二つあるんですね。多分、うちは前者だと思います。
これもまた(1)が関係してるんですね。
こんな私でも理解できました。本当にありがとうございました!
No.1
- 回答日時:
> これが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なども受理できたのでは、と思います。
(むちゃくちゃ自信ないですけど (^^ゞ)
早くこれらの知識をコンピューター上で試してみたいです。
ありがとうございました!
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- PHP ここで言う空文字の意味とは? 1 2022/08/05 16:27
- Visual Basic(VBA) エクセルVBAについて 2 2023/01/31 16:21
- 物理学 高一の物理基礎に関する質問です。 100m走の記録が10秒であった時、この選手が走っている最中に瞬間 7 2023/05/23 12:43
- 化学 結晶場理論で真空状態から例えば8面体配位でt2gが安定化するのはなぜでしょうか? 1 2023/04/30 19:09
- Excel(エクセル) Excelの空文字判定について 7 2023/01/06 13:25
- PHP 空文字 "" ですが 空文字の意味を教えてください。 3 2022/08/05 03:51
- Visual Basic(VBA) Excel VBA キーワードから列を取得して、さらに空欄行を非表示にする 3 2022/10/21 22:49
- その他(プログラミング・Web制作) プログラミング pythonの問題について 2 2022/04/19 00:41
- WordPress(ワードプレス) WordpressでYouTubeの埋め込みができない。 1 2022/10/26 01:08
- Java Java 南京錠 2 2023/02/04 11:46
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
selectにline-heightがきかない...
-
レイノルズ数が4000より大きい...
-
oppo reno 7A
-
回復ドライブに保存されるもの
-
d3dx9_40.dllが見つからなかっ...
-
フォルダーに緑のレ点と赤の✖が...
-
ipodnanoの画面が真っ暗です!!
-
自動構成スクリプト(proxy.pac...
-
VB.NETで、システムのレジスト...
-
VB.net webアプリケーション 戻...
-
[python]スクリプトから起動で...
-
keygen.exeが実行されない
-
java起動時にフリーズします
-
教えてください アプリケーショ...
-
NTTの電話番号検索ソフトですが...
-
Windows2003,XPの32bitから64bit化
-
ipadかandroidか
-
iPhoneの自動回転機能を切りたい
-
子画面を読んだ後親画面のRecor...
-
タスクマネージャーが消えた。(...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
レイノルズ数が4000より大きい...
-
gcc13.2のバグ?
-
オートマトン: npdaとdpdaの違い
-
google maps editorをtableタグ...
-
selectにline-heightがきかない...
-
Objective-c 画面遷移について
-
一次遷移の特徴として裸地から...
-
CSSが反映されない(IE)
-
リスティングいたずらクリック防止
-
jqueryuiのスライダーのバグに...
-
MacBookでフルスクリーンを 解...
-
JavaScriptを拒否するユーザー
-
プルダウンメニューが動画の下...
-
自らのViewControllerにsegueする
-
oppo reno 7A
-
フォルダーに緑のレ点と赤の✖が...
-
特定ユーザに対してのみアプリ...
-
VB.net webアプリケーション 戻...
-
Beckyのアドレス帳を上下に移動...
-
Linuxでの開発環境構築や設定の...
おすすめ情報