投稿者: 
文脈自由文法について
前回はプッシュダウン・オートマトン (pushdown automaton)について見てみた。プッシュダウン・オートマトンの特徴は「スタック」という構造のおかげで複雑な表現が可能になるということであった。このプッシュダウン・オートマトンのレベルで表現可能になる文法レベルを文脈自由文法 (context-free grammar, CFG)と言う。
今回はこの文脈自由文法についてまとめる。
文脈自由文法は下記の形を取る。（厳密にはチョムスキー標準形と呼ばれる型である。）
A → BC (A, B, C は非終端記号)
A → b (Aは非終端記号, b は終端記号)
非終端記号とはそれ以上の分解が可能な構造を表すための記号である。例えば、NounやVerbという要素等はさらに具体的な要素 (a boy, walk)に分解が可能だ。他方、終端記号とはそれ以上の分解が不可能な構造を表すための記号である。例えば、boy, walk はこれ以上の分解ができない、つまり終端の要素だと考えることができる。
このような表現を行うことでアルゴリズム等の記述を簡素化できるというメリットがある。
参考文献
- 北研二. (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/ - Sipser, M., & 太田他. (2000). 計算理論の基礎.