「弱文脈依存言語」の版間の差分

(言語学的研究)
=== Control Language Hierarchy の Level 2 言語クラス ===
下記の4つの弱文脈依存文法は同じ弱生成力を持つ事が証明されている (Joshi et al 1994):
* [[木接合文法]] (TAG) – Aravind Joshi
* [[w:en:Combinatory categorial grammar | Combinatory Categorial Grammar]] (CCG) – Mark Steedman
* Head GrammarGrammars (HG) – Carl Pollard
* Linear Indexed Grammar (LIG) – Gerald Gazdar
これらの文法の生成力は Weir の Control Language Hierarchy の Level 2 言語クラスに対応する。なお CLH の Level 1 は文脈自由言語であり、この4つのフレームワークが共有する言語クラスは弱文脈依存文法では生成力が一番弱い方にあたる。このクラスの言語は <math> \{ a^n b^n c^n : n \ge 0 \} </math> や <math> \{ a^n b^n c^n d^n : n \ge 0 \} </math> の文字列を生成する事が出来る。対応するオートマトンは Embedded Pushdown Automaton (EPDA) である。
この4つフレームワークの内、特に木接合文法とCCGはこれらをそれぞれ用いてまとまった言語学的研究がなされている。([http://www.cis.upenn.edu/~xtag/], [http://groups.inf.ed.ac.uk/ccg/publications.html]など)
309

回編集