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) 正規表現できなかった {an bn ; n は自然数} は文脈自由言語です.なお,{an bn cn; n は自然数} は文脈自由文法で記述できない文脈依存言語です.
(4) 句構造文法の書き換え規則は [0-1] 第4章の式より [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
※コメント投稿者のブログIDはブログ作成者のみに通知されます