下記のようなオートマトンがあります。
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ベストアンサー
- 回答日時:
先の2つの御質問からすると、non-deterministic(非決定的)なPDAを考えているわけですよね。
非決定的なオートマトンでは、「1つの入力系列に対して複数の遷移経路が考えられるが、そのうち1つでも受理状態で遷移が終了する経路が存在すれば、オートマトンはその入力を受理する」と考えます。
baabbaabの例であれば、"b"しか入力されていない状態、"ba"まで入力された状態、...、"baabbaab"まで入力されてしまった状態、のどこで(2)の遷移をやってもいいんです。
そのうち"baab"の状態で(2)の遷移をすれば受理状態で遷移が終了するので、このオートマトンは"baabbaab"を受理するといえるわけです。
> それは(2)を
> ....
> を付け加えればよいですか? (多分、そうですよね?)
そこはそれで合っていると思いますよ。
ああ! ではnfaとまったく同じ考え方なんですね。
non-deterministic(非決定的)というのはそういうことなんですね。
ということは、
スタックが'z'になって後はλの入力さえあれば受理、という状態もある一方で、
今まで入力された文の逆文の入力待ちになっている状態も同時に存在する、ということですね。
理解できました。
これからももっともっと勉強してみます。
本当にありがとうございました!
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
正負を反転させて出力するプロ...
-
Eclipseコンソール表示を、リセ...
-
C++ scanfで止まらない
-
Linuxで入力待ちなしkeyread関...
-
WindowsでEOF
-
C言語のプログラム作成の課題...
-
プログラミング初心者です。 Py...
-
java初心者です。入力されたの...
-
VisualStudio2019のコードアナ...
-
コマンドプロンプトからのEOFの...
-
C言語・YesNo入力のループで解...
-
Linuxプログラミングで、キーボ...
-
コマンドラインから引数を渡し...
-
入力候補を表示させるには・・・?
-
至急教えてください。プログラ...
-
scanfについて
-
ヒントをください!
-
scanf関数について
-
小数か整数かを判定する方法
-
C言語の勉強しています。すみま...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正負を反転させて出力するプロ...
-
プログラミング初心者です。 Py...
-
数字以外が入力されたらエラー...
-
Eclipseコンソール表示を、リセ...
-
Excel VBAで、Application.Inpu...
-
*をユーザーが入力した数字の数...
-
java初心者です。入力されたの...
-
Linuxで入力待ちなしkeyread関...
-
batプログラム上で文字列を入力...
-
WindowsでEOF
-
Userformの入力順序をタブオー...
-
コマンドプロンプトからのEOFの...
-
EDITコントロールで入力できる...
-
VisualStudio2019のコードアナ...
-
電卓の小数点
-
Eclipseでコマンドラインを入力...
-
小数か整数かを判定する方法
-
cout関数を使っているのですが...
-
UWSCで変数をキー入力
-
ワードで文字を入力する時の変...
おすすめ情報