オートマトン (4)

sys6.pdf sys.pdf sys-s.pdf 記事一覧

逆ポーランド記法の式の導出木

#63: 文脈自由文法

一般の句構造文法は複雑過ぎるので，正規表現の次に簡単な文脈自由言語を生成する文脈自由文法について説明しました．

補足：(1) 句構造文法を表わす 4-tuple に用いる記号は定まっていないようです．[0-1] では (N, T, P, S)，[4-1] では (N, Σ, P, S)，[4-3] では (V, Σ, R, S) です．1960年代に教わった [4-11] の (V, Σ, P, σ) のV は [4-3] の V と異なり N ∪ T でした．
(2) 逆ポーランド記法や文脈依存文法には言及しませんでした．
(3) 正規表現できなかった {aⁿ bⁿ ; n は自然数} は文脈自由言語です．なお，{aⁿ bⁿ cⁿ; n は自然数} は文脈自由文法で記述できない文脈依存言語です．
(4) 句構造文法の書き換え規則は [0-1] 第４章の式より [4-4] の式の方が正しいと思います --- (N ∪ T)⁺ でなく (N ∪ T)^* - T^*．

[4-1] 形式文法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E5%BD%A2%E5%BC%8F%E6%96%87%E6%B3%95
[4-2] チョムスキー階層 - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A7%E3%83%A0%E3%82%B9%E3%82%AD%E3%83%BC%E9%9A%8E%E5%B1%A4
[4-3] 文脈自由文法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%96%87%E8%84%88%E8%87%AA%E7%94%B1%E6%96%87%E6%B3%95
[4-4] 11回目：句構造文法とチューリング機械
  http://www.enel.ucalgary.ca/People/far/Lectures/Automaton/PDF/11kaime.pdf
[4-5] 逆ポーランド記法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95
-----------------------------------
[4-6] 形式言語 - Wikipedia
  http://ja.wikipedia.org/wiki/%E5%BD%A2%E5%BC%8F%E8%A8%80%E8%AA%9E
[4-7] 文脈依存文法
  http://ja.wikipedia.org/wiki/%E6%96%87%E8%84%88%E4%BE%9D%E5%AD%98%E6%96%87%E6%B3%95
[4-8] 生成文法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E7%94%9F%E6%88%90%E6%96%87%E6%B3%95
[4-9] 一般化句構造文法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E4%B8%80%E8%88%AC%E5%8C%96%E5%8F%A5%E6%A7%8B%E9%80%A0%E6%96%87%E6%B3%95
[4-10] 主辞駆動句構造文法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E4%B8%BB%E8%BE%9E%E9%A7%86%E5%8B%95%E5%8F%A5%E6%A7%8B%E9%80%A0%E6%96%87%E6%B3%95
[4-11] The Mathematical Theory of Context-Free Languages
  http://dl.acm.org/citation.cfm?id=1102023