Control Language Hierarchy の Level 2 言語クラス
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2014/01/26 16:07 UTC 版)
「弱文脈依存言語」の記事における「Control Language Hierarchy の Level 2 言語クラス」の解説
下記の4つの文法は同じ弱生成力を持つ事が証明されている (Joshi et al 1994): 木接合文法 (TAG) – Aravind Joshi Combinatory Categorial Grammar (CCG) – Mark Steedman Head Grammars (HG) – Carl Pollard Linear Indexed Grammar (LIG) – Gerald Gazdar これらの文法の生成力は Weir の Control Language Hierarchy の Level 2 言語クラスに対応する。なお CLH の Level 1 は文脈自由言語であり、この4つのフレームワークが共有する言語クラスは弱文脈依存文法の中でも生成力が一番弱い方にあたる。このクラスの言語は や の文字列を生成する事が出来る。対応するオートマトンは Embedded Pushdown Automaton (EPDA) である。 この4つフレームワークのうち、特に木接合文法とCCGはこれらを用いてそれぞれまとまった言語学的研究がなされている。(, など)
※この「Control Language Hierarchy の Level 2 言語クラス」の解説は、「弱文脈依存言語」の解説の一部です。
「Control Language Hierarchy の Level 2 言語クラス」を含む「弱文脈依存言語」の記事については、「弱文脈依存言語」の概要を参照ください。
- Control Language Hierarchy の Level 2 言語クラスのページへのリンク