プッシュダウンオートマトン(PDA)を図を使って分かりやすく解説！

この記事のまとめ

・プッシュダウンオートマトンとは「スタックを持った非決定性有限オートマトン」

・スタックとは簡単に言えば「データを後入れ先出しする構造」のこと

・受理状態においてスタックが空になるような入力文字が受理される

プッシュダウンオートマトン(PDA)とは？

プッシュダウンオートマトン(PushDown Automaton : PDA)とは「スタックを持った非決定性有限オートマトン」です。

今までに習ったオートマトンは次のようなものでした。このオートマトンは入力文字列が$ab$なら受理されます。

それに対して、プッシュダウンオートマトンとは次のようなものです。

今までのオートマトンと比べると何やら複雑で、難しいように感じるかもしれませんが、スタックが追加されただけなので、恐れる必要はありません。

まずは、スタックについて説明します！

先生

スタックとは？

スタックとは簡単に言えば「データを後入れ先出しする構造」です。次の図を見てください。

スタックにデータを追加することを「Push」、データを取り出すことを「Pop」と言います。そして、$a$より後に追加した$b$が先に取り出されているので、「後入れ先出し＝Last In First Out(LIFO)」です。

プッシュダウンオートマトンはこの構造をオートマトンに組み込んだものなのです。

プッシュダウンオートマトンの仕組み

プッシュダウンオートマトンは以下のようなものでした。

各状態間に書いてある$\varepsilon, \varepsilon \rightarrow \$ $などのことを「遷移関数」と呼び、各記号は次のような意味を持っています。

つまり、入力文字とPopされる文字が遷移関数と合致していれば、状態が遷移されて右辺の文字がPushされるというわけです。

$\varepsilon$と書いてある場合は、その条件は無いのと同じです。例えば、$\varepsilon, \varepsilon \rightarrow \$ $ならば、入力文字やPopされる文字が何であろうと、遷移関数の左辺の条件が満たされるということになり、$ \$ $がPushされます。これは非決定性オートマトンの$\varepsilon$遷移と同じですね。