下記のようなオートマトンがあります。
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で質問しましょう!
似たような質問が見つかりました
- WordPress(ワードプレス) Wordpressの記事URLを自由に決めたい 3 2022/06/02 12:05
- Excel(エクセル) エクセルで文字の一部を赤から白に変えるマクロを教えて下さい。 2 2022/10/08 23:01
- Java Java 南京錠 2 2023/02/04 11:46
- その他(プログラミング・Web制作) プログラミング pythonの問題について 2 2022/04/19 00:41
- その他(スマートフォン・携帯電話・VR) 全部入りでも夜間の動画性能がいいスマホありますか? 5 2022/04/04 16:33
- C言語・C++・C# プログラミングの問題です。至急教えてください。 /***から***/の部分をプログラミングにしてほし 1 2022/10/13 11:48
- Excel(エクセル) Excelにて、セルに入力してある文字の中から文字と最後の数字のみ切り取り貼り付けるVBA 5 2022/12/27 08:40
- Excel(エクセル) 条件に合った数値の合計を表示させたい関数と条件指定の方法 3 2023/05/13 16:07
- Visual Basic(VBA) excelにて、特定の列に数字入力してあれば、入力してある行コピーして 別ファイルに張り付ける 2 2022/08/11 05:33
- Word(ワード) Windows11キーボードの調子が悪いので治し方を教えてください。 【症状】 1つ目 キーボードの 5 2022/07/03 14:51
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
数字以外が入力されたらエラー...
-
*をユーザーが入力した数字の数...
-
Eclipseコンソール表示を、リセ...
-
Userformの入力順序をタブオー...
-
scanfが2回使えない・・・?;
-
C++のcinの動作
-
C言語でつるかめ算をするにはど...
-
MinGWのC言語でCTRL+Zで処理が...
-
cout関数を使っているのですが...
-
プログラミング初心者です。 Py...
-
意味のよく分らないソース
-
getc 等の違い
-
C言語について
-
2進数の1の数を数える問題
-
C言語で入門の本を読んだあとは...
-
double型が正常に認識されてい...
-
scanfの入力をgets関数で読み捨...
-
漢字のソートについて
-
C言語 入力した値から0までの数...
-
WindowsでEOF
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
*をユーザーが入力した数字の数...
-
正負を反転させて出力するプロ...
-
数字以外が入力されたらエラー...
-
プログラミング初心者です。 Py...
-
double型が正常に認識されてい...
-
java初心者です。入力されたの...
-
Eclipseコンソール表示を、リセ...
-
scanfが2回使えない・・・?;
-
C言語scanf_sで何故か2回入力に...
-
if文の条件にscanf関数を使うと…?
-
プログラミングの問題です 「金...
-
Linuxで入力待ちなしkeyread関...
-
ワードで文字を入力する時の変...
-
cout関数を使っているのですが...
-
batプログラム上で文字列を入力...
-
Userformの入力順序をタブオー...
-
scanf が無視されます
-
C言語 逆ピラミッドの作り方
-
gets_sがうまく動かない
-
Excel VBAで、Application.Inpu...
おすすめ情報