こんにちはの方もこんばんはの方もようこそ、イカスミです。
大学生、特に情報系学生の皆さん、形式言語の授業で、プッシュダウンオートマトンって何？となった経験はありませんか？
この記事では、そんな方に向けて、情報系大学生の僕がプッシュダウンオートマトンについて解説したいと思います。
この記事で解決できる悩み
- プッシュダウンオートマトンがわからない
- プッシュダウンオートマトンの問題が解けない
この記事では、こちらの参考書を基準としていますので、余裕がある方は手にとってみてください。
プッシュダウンオートマトンとは
プッシュダウンオートマトンは、有限オートマトンにスタックと呼ばれる記憶装置を付け加えたものです。
有限オートマトンについては、こちらの記事で解説しているので、参考にしてみてください。
-
-
【現役大学生が決定性有限オートマトンをわかりやすく解説します】形式言語とオートマトン
こんにちはの方もこんばんはの方もようこそ、イカスミです。 大学生、特に情報系学生の皆さん、形式言語の授業で、決定性有限オートマトンって何？となった経験はありませんか？ この記事では、そんな方に向けて、 ...
続きを見る
-
-
【現役大学生が非決定性有限オートマトンをわかりやすく解説します】形式言語とオートマトン
こんにちはの方もこんばんはの方もようこそ、イカスミです。 大学生、特に情報系学生の皆さん、決定性有限オートマトンはわかるけど、非決定性有限オートマトンって何？となった経験はありませんか？ この記事では ...
続きを見る
スタックとは、「先入れ後出し」の記憶装置です。
データをスタックに入れ、最後に格納したデータから取出します。
有限オートマトンとの違い
プッシュダウンオートマトンは、スタックを用いて入力を記憶できるので、有限オートマトンよりも多くの言語を表現できます。
また、状態遷移図も異なります。
有限オートマトンはこのような状態遷移図でしたが、
プッシュダウンオートマトンの状態遷移図はこのようになります。
記述する記号が増えていますね。ここでは、λはεを表します。
例えば、0, 0：λ という遷移関数は、入力が0、スタックの先頭記号が0の場合、スタックの先頭記号を取り除くことを表します。
0, 1：01は、入力が0、スタックの先頭記号が1の場合、スタックに1を加えることを表します。
大体の場合、受理状態への遷移は、スタックが空の場合にε遷移で行われます。
このように、プッシュダウンオートマトンの状態遷移図は、スタック記号の記憶・削除を上手く用いることが重要となります。
例題
例題を用いて、プッシュダウンオートマトンをわかりやすく解説します。
例題：長さが偶数の回分を受理するプッシュダウンオートマトンの状態遷移図を示せ。
長さが偶数なので、入力を半分に分けて考えます。
前半の入力はスタックへの記憶、後半の入力はスタックの記号を削除するために用います。
そのためには、次の3つの状態が必要となります。
- q0：前半の入力をスタックに記憶する状態
- q1：後半の入力を用いて、q1で記憶したスタック記号を削除する状態
- q2：受理状態
q1では入力をスタックに記憶するので、遷移は自分自身に向かいます。
q2ではスタック記号と入力が一致した場合、スタック記号を削除します。
この操作を状態遷移図にすると、このようになります。
次に、各状態をつなぎ合わせます。
q1からq2への遷移は、ε遷移で行います。
何故かというと、q1で入力の前半、q2で入力の後半を使うので、もし入力を使用してしまうと、q2で使用する入力が足りなくなってしまうからです。
q3は受理状態なので、q2からq3への遷移は、スタックが空の場合にε遷移を行います。
最終的な状態遷移図は、このようになります。
q0で前半の入力を記憶し、ε遷移によりq1に遷移します。
q1で後半の入力を用いてスタック記号を削除します。
入力が全て消費され( = 入力がない)、かつスタック記号が空の場合に、q2に遷移し、入力が受理されます。
まとめ
この記事では、プッシュダウンオートマトンについて解説しました。まとめると、
- プッシュダウンオートマトンは、有限オートマトンにスタックを付け加えたもの
- 状態遷移図は、スタック記号の追加・削除を利用する
この記事が、皆さんの学習の参考になれば幸いです。
最後まで読んで頂き、ありがとうございました。