言語クラス

(表1)

 

 
文法のタイプ 書き換え規則 計算モデル 計算量 表現力
正規文法(3型) tex2html_wrap_inline181 FSA O(n) 文節
tex2html_wrap_inline185
文脈自由文法(2型) tex2html_wrap_inline187 PDA tex2html_wrap_inline189 以下 自然言語の大部分
文脈依存文法(1型) tex2html_wrap_inline191 LBA tex2html_wrap_inline193 以下
tex2html_wrap_inline195 (k > 1)
帰納的加算集合(0型) tex2html_wrap_inline191 TM 決定不能
表: 主な形式文法のタイプとその性質


tex2html_wrap_inline201

next up previous
Next: 文脈自由文法の解析方法 Up: 構文解析技術の概要 Previous: 構文解析技術の概要

Masahiro Araki
Wed May 13 08:22:57 JST 1998