投稿者: 
プッシュダウンオートマトンについて
今まで、下記の有限オートマトンと正則文法を見てきた。
- 有限オートマトン (finite automaton)
正則文法 (regular grammar) - プッシュダウン・オートマトン (pushdown automaton)
文脈自由文法 (context-free grammar) - 線形拘束オートマトン (linear bounded automaton)
文脈依存文法 (context-sensitive grammar) - チューリング機械 (Turing Machine)
句構造文法 (phrase structure grammar)
(北 1999)
本稿ではプッシュダウン・オートマトン (pushdown automaton)についてまとめたい。プッシュダウン・オートマトンはPDAとも呼ばれ、有限オートマトン (Finite Automaton) に「スタック」という構造を追加したものになる。この構造を持つことにより、正則言語よりも複雑な構造(例えば入れ子構造)などの表現が可能になる。
また、複雑な表現が可能になるため文法の記述力が強まる。これが文脈自由文法 (context-free grammar)の表現を可能にする。
参考文献
- 北研二. (1999). 確率的言語モデル. 言語と計算, 4.
- 電子情報通信学会 知識ベース 6群2編 計算論とオートマトン
https://www.ieice-hbkb.org/portal/6%e7%be%a4%e3%80%80%e3%82%b3%e3%83%b3%e3%83%94%e3%83%a5%e3%83%bc%e3%82%bf-%e5%9f%ba%e7%a4%8e%e7%90%86%e8%ab%96%e3%81%a8%ef%be%8a%ef%bd%b0%ef%be%84%ef%be%9e%ef%bd%b3%ef%bd%aa%ef%bd%b1/6%e7%be%a42%e7%b7%a8%e3%80%80%e8%a8%88%e7%ae%97%e8%ab%96%e3%81%a8%e3%82%aa%e3%83%bc%e3%83%88%e3%83%9e%e3%83%88%e3%83%b3/