「弱文脈依存言語」の版間の差分
特徴 |
文法フレームワーク |
||
1行目: | 1行目: | ||
'''弱文脈依存文法''' (Mildly Context-sensitive Grammars) とは、 Joshi (1985) の提案した[[自然言語]]の理論に必要であろう特徴を持った[[形式文法]]の総称で、そのような[[文法]]によって定義づけられる言語クラスが'''弱文脈依存言語''' (Mildly Context-sensitive Languages) である。 |
'''弱文脈依存文法''' (Mildly Context-sensitive Grammars) とは、 Joshi (1985) の提案した[[自然言語]]の理論に必要であろう特徴を持った[[形式文法]]の総称で、そのような[[文法]]によって定義づけられる言語クラスが'''弱文脈依存言語''' (Mildly Context-sensitive Languages) である。 |
||
[[チョムスキー階層]]の[[文脈依存言語]]の中でも[[文脈自由言語]]に一番近い部分にあたり、[[Indexed Languages]] (IL) ほどは生成力がない。Joshi の[[木接合文法]] (TAG) の研究の中から生まれた概念だが、TAG以外にもこのクラスの言語を |
[[チョムスキー階層]]の[[文脈依存言語]]の中でも[[文脈自由言語]]に一番近い部分にあたり、[[Indexed Languages]] (IL) ほどは生成力がない。Joshi の[[木接合文法]] (TAG) の研究の中から生まれた概念だが、TAG以外にもこのクラスの言語を生成する文法が[[言語学]]および形式言語論において多数提案されている。また、形式言語・[[オートマトン]]論的な研究も進んでおり、Weir (1992) によって弱文脈依存言語の性質を持つ言語の階層 (Weir's Control Language Hierarchy) が対応するオートマトンと共に定義づけられている。 |
||
== 特徴 == |
== 特徴 == |
||
11行目: | 10行目: | ||
# 弱文脈依存の言語は定数的増加 (constant growth) 特性を持つ。 |
# 弱文脈依存の言語は定数的増加 (constant growth) 特性を持つ。 |
||
弱文脈依存言語の研究の背景には、自然言語が文脈自由言語の性質を多く持つにも関わらず、弱生成力が文脈自由文法を超えるケースがある事がある。上記の下3点はその文脈自由の持つ性質を一般化したものとも言える。 |
弱文脈依存言語の研究の背景には、自然言語が文脈自由言語の性質を多く持つにも関わらず、弱生成力が文脈自由文法を超えるケースがある事がある。上記の下3点はその文脈自由の持つ性質を一般化したものとも言える。 |
||
== 弱文脈依存な文法フレームワーク == |
|||
= Control Language Hierarchy の Level 2 言語クラス = |
|||
下記の4つの弱文脈依存文法は同じ弱生成力を持つ事が証明されている (Joshi et al 1994): |
|||
* 木接合文法 (TAG) |
|||
* Combinatory Categorial Grammar (CCG) |
|||
* Head Grammar (HG) |
|||
* Linear Indexed Grammar (LIG) |
|||
これらの文法の生成力は 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はこれらを用いたまとまった言語学的研究がなされている。 |
|||
== Reference == |
== Reference == |
||
A. K. Joshi |
* 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. |
|||
2008年4月26日 (土) 22:46時点における版
弱文脈依存文法 (Mildly Context-sensitive Grammars) とは、 Joshi (1985) の提案した自然言語の理論に必要であろう特徴を持った形式文法の総称で、そのような文法によって定義づけられる言語クラスが弱文脈依存言語 (Mildly Context-sensitive Languages) である。
チョムスキー階層の文脈依存言語の中でも文脈自由言語に一番近い部分にあたり、Indexed Languages (IL) ほどは生成力がない。Joshi の木接合文法 (TAG) の研究の中から生まれた概念だが、TAG以外にもこのクラスの言語を生成する文法が言語学および形式言語論において多数提案されている。また、形式言語・オートマトン論的な研究も進んでおり、Weir (1992) によって弱文脈依存言語の性質を持つ言語の階層 (Weir's Control Language Hierarchy) が対応するオートマトンと共に定義づけられている。
特徴
Joshi (1985) は以下の特徴を弱文脈依存文法を定義づけるものとしてあげている:
- 弱文脈依存言語は文脈自由言語を正当に包含する。
- 弱文脈依存の言語は多項式時間で認識可能である。
- 弱文脈依存文法は特定の依存関係、入れ子状と限られた種類の交差、のみを捉える事が出来る。
- 弱文脈依存の言語は定数的増加 (constant growth) 特性を持つ。
弱文脈依存言語の研究の背景には、自然言語が文脈自由言語の性質を多く持つにも関わらず、弱生成力が文脈自由文法を超えるケースがある事がある。上記の下3点はその文脈自由の持つ性質を一般化したものとも言える。
弱文脈依存な文法フレームワーク
Control Language Hierarchy の Level 2 言語クラス
下記の4つの弱文脈依存文法は同じ弱生成力を持つ事が証明されている (Joshi et al 1994):
- 木接合文法 (TAG)
- Combinatory Categorial Grammar (CCG)
- Head Grammar (HG)
- Linear Indexed Grammar (LIG)
これらの文法の生成力は Weir の Control Language Hierarchy の Level 2 言語クラスに対応する。なお CLH の Level 1 は文脈自由言語であり、この4つのフレームワークが共有する言語クラスは弱文脈依存文法では生成力が一番弱い方にあたる。このクラスの言語は や の文字列を生成する事が出来る。対応するオートマトンは Embedded Pushdown Automaton (EPDA) である。 この4つの内、特に木接合文法とCCGはこれらを用いたまとまった言語学的研究がなされている。
Reference
- 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.