弱文脈依存言語

Joshi (1985) は以下の特徴を弱文脈依存文法を定義づけるものとしてあげている：

1. 弱文脈依存言語は文脈自由言語を正当に包含する。
2. 弱文脈依存の言語は多項式時間で認識可能である。
3. 弱文脈依存文法は特定の依存関係、入れ子状と限られた種類の交差、のみを捉える事が出来る。
4. 弱文脈依存の言語は定数的増加 (constant growth) 特性を持つ。

弱文脈依存言語の研究の背景には、自然言語が文脈自由言語の性質を多く持つにもかかわらず、その弱生成力が文脈自由文法を超えるケースがある事がある。特に、スイスドイツ語で発見された格の一致を伴う交差依存関係は弱文脈依存文法の必要性を強く示唆する。上記の下３点はその文脈自由の持つ性質を若干拡張したものとも言える。

下記の４つの文法は同じ弱生成力を持つ事が証明されている (Joshi et al 1994)：

• 木接合文法 (TAG) – Aravind Joshi
• 組合せ範疇文法 (CCG) – Mark Steedman
• Head Grammars (HG) – Carl Pollard
• Linear Indexed Grammar (LIG) – Gerald Gazdar

これらの文法の生成力は Weir の Control Language Hierarchy の Level 2 言語クラスに対応する。なお CLH の Level 1 は文脈自由言語であり、この４つのフレームワークが共有する言語クラスは弱文脈依存文法の中でも生成力が一番弱い方にあたる。このクラスの言語は ${\displaystyle \{a^{n}b^{n}c^{n}:n\geq 0\}}$ や ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}:n\geq 0\}}$ の文字列を生成する事が出来る。対応するオートマトンは Embedded Pushdown Automaton (EPDA) である。 この４つフレームワークのうち、特に木接合文法とCCGはこれらを用いてそれぞれまとまった言語学的研究がなされている。(, など)

• A. K. Joshi. Tree adjoining grammars: how much context-sensitivity is required to provide reasonable structural descriptions? In D. R. Dowty, L. Karttunen, and A. Zwicky, editors, Natural Language Parsing, pages 206–250. Cambridge University Press, Cambridge, 1985.
• Josh, A & Vijay-Shanker, K. & Weir, David (1994), "The Equivalence of Four Extensions of Context-Free Grammars", Mathematical Systems Theory 27 (6): 511–546; originally presented at The processing of Linguistic Structure at Santa Cruz CA, January 1987.
• D. J. Weir. A geometric hierarchy beyond context-free languages. Theor. Comput. Sci., 104(2):235–261, 1992.

この項目は、言語学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（ウィキポータル 言語学）。

• 表示
• 編集