プッシュダウンオートマトン(PDA)とは?
プッシュダウンオートマトン(PushDown Automaton : PDA)とは「スタックを持った非決定性有限オートマトン」です。
今までに習ったオートマトンは次のようなものでした。このオートマトンは入力文字列が$ab$なら受理されます。
![](https://www.krrk0.com/wp-content/uploads/2021/08/image-29.png)
それに対して、プッシュダウンオートマトンとは次のようなものです。
![](https://www.krrk0.com/wp-content/uploads/2021/08/image-28.png)
今までのオートマトンと比べると何やら複雑で、難しいように感じるかもしれませんが、スタックが追加されただけなので、恐れる必要はありません。
まずは、スタックについて説明します!
![先生](https://www.krrk0.com/wp-content/uploads/2021/03/2315a25cc82a6999153f668aad359dc6-300x267.png)
スタックとは?
スタックとは簡単に言えば「データを後入れ先出しする構造」です。次の図を見てください。
![](https://www.krrk0.com/wp-content/uploads/2021/08/image-9.png)
スタックにデータを追加することを「Push」、データを取り出すことを「Pop」と言います。そして、$a$より後に追加した$b$が先に取り出されているので、「後入れ先出し=Last In First Out(LIFO)」です。
プッシュダウンオートマトンはこの構造をオートマトンに組み込んだものなのです。
プッシュダウンオートマトンの仕組み
プッシュダウンオートマトンは以下のようなものでした。
![](https://www.krrk0.com/wp-content/uploads/2021/08/image-30.png)
各状態間に書いてある$\varepsilon, \varepsilon \rightarrow \$ $などのことを「遷移関数」と呼び、各記号は次のような意味を持っています。
![](https://www.krrk0.com/wp-content/uploads/2021/08/image-10.png)
つまり、入力文字とPopされる文字が遷移関数と合致していれば、状態が遷移されて右辺の文字がPushされるというわけです。
$\varepsilon$と書いてある場合は、その条件は無いのと同じです。例えば、$\varepsilon, \varepsilon \rightarrow \$ $ならば、入力文字やPopされる文字が何であろうと、遷移関数の左辺の条件が満たされるということになり、$ \$ $がPushされます。これは非決定性オートマトンの$\varepsilon$遷移と同じですね。
![くるる](https://www.krrk0.com/wp-content/uploads/2021/08/3e25b0844a88378bf1647d62f04a7b94.png)
ところでスタックはどうやって使われてるんすか?
説明しましょう!
![先生](https://www.krrk0.com/wp-content/uploads/2021/06/a9e9cc2b6b3933040649ee27362ea1c4-4.png)
例えば、オートマトンに「$ab$」を入力したとします。すると、スタックとオートマトンは次のような対応になっています。
![](https://www.krrk0.com/wp-content/uploads/2021/08/image-31.png)
スタックは図のように遷移関数によってPushやPopが行われます。初期状態は空で、受理状態でも空になってないといけません。
今回の入力文字列「$ab$」はこの条件を満たすので、このオートマトンに受理されます。
非決定性オートマトンにスタックが追加されただけで、やることは非決定性オートマトンとあまり変わりませんね!
![先生](https://www.krrk0.com/wp-content/uploads/2021/07/0a1deaec26b673bf1d79002197a6953f.png)
まとめ
・プッシュダウンオートマトンとは「スタックを持った非決定性有限オートマトン」
・スタックとは簡単に言えば「データを後入れ先出しする構造」のこと
・受理状態においてスタックが空になるような入力文字が受理される
以下の記事もおすすめです!
・プッシュダウンオートマトンとは「スタックを持った非決定性有限オートマトン」
・スタックとは簡単に言えば「データを後入れ先出しする構造」のこと
・受理状態においてスタックが空になるような入力文字が受理される