文脈依存文法

Type of a formal grammar

文脈依存文法（CSG）は、任意の生成規則の左辺と右辺が終端記号と非終端記号の文脈に囲まれる形式文法である。文脈依存文法は文脈自由文法よりも汎用的であり、CSGで記述できても文脈自由文法では記述できない言語が存在する。文脈依存文法は（同じ意味で）非制限文法ほど汎用的ではない。したがって、CSGはチョムスキー階層において文脈自由文法と非制限文法の中間に位置する。^[1]

文脈依存文法、あるいはそれと同義の非縮約文法や線形有界オートマトンで記述できる形式言語は、文脈依存言語と呼ばれる。一部の教科書ではCSGを非縮約と定義しているが^{[2] [3] [4] [5] 、これは}ノーム・チョムスキーが1959年に定義した方法ではない。^{[6] [7]}この定義の選択は、生成される言語という点では違いを生じない（つまり、2つの定義は弱く同値である）が、どのような文法が構造的に文脈依存と見なされるかという点では違いを生じさせる。後者の問題は1963年にチョムスキーによって分析された。^{[8] [9]}

チョムスキーは、自然言語の統語論を記述する方法として文脈依存文法を導入した。自然言語では、文脈に応じて単語が特定の場所で適切であるか否かがしばしば問題となる。ウォルター・サヴィッチは、「文脈依存」という用語は誤解を招くと批判し、「非消去」という表現の方が文脈依存文法と非制限文法の違いをより適切に説明できると提唱した。^[10]

言語の特定の特徴（例えば、クロスシリアル依存性）は文脈自由ではないことはよく知られていますが、自然言語に見られる文脈依存性を捉えるためにCSGの表現力がどの程度必要かは未解決の問題です。この分野におけるその後の研究は、より計算量的に扱いやすい軽度文脈依存言語に焦点が当てられてきました。^{[要出典]一部の}ビジュアルプログラミング言語の構文は、文脈依存グラフ文法によって記述できます。^[11]

正式な定義

正式な文法

非終端記号のセット、終端記号のセット、生成規則のセット、および開始記号を使用して、形式文法をと表記します。 ${\displaystyle G=(N,\Sigma ,P,S)}$ ${\displaystyle N}$ ${\displaystyle \Sigma }$ ${\displaystyle P}$ ${\displaystyle S\in N}$

文字列 は、Pのある生成規則を適用してuからvを取得できる場合、つまり かつ である場合 ( は生成規則、 はそれぞれ文字列の影響を受けない左側と右側の部分) 、直接 を生成する、または と表記される文字列 に直接派生します。より一般的には、生成規則を繰り返し適用してuからvを取得できる場合、つまりn ≥ 0 のある文字列 に対して である場合、 uはvを生成する、または と表記される文字列に派生すると言われます。言い換えると、関係 は関係 の反射的推移閉包です。 ${\displaystyle u\in (N\cup \Sigma )^{*}}$ ${\displaystyle v\in (N\cup \Sigma )^{*}}$ ${\displaystyle u\Rightarrow v}$ ${\displaystyle u=\gamma L\delta }$ ${\displaystyle v=\gamma R\delta }$ ${\displaystyle (L\to R)\in P}$ ${\displaystyle \gamma ,\delta \in (N\cup \Sigma )^{*}}$ ${\displaystyle u\Rightarrow ^{*}v}$ ${\displaystyle u=u_{0}\Rightarrow ...\Rightarrow u_{n}=v}$ ${\displaystyle u_{1},...,u_{n-1}\in (N\cup \Sigma )^{*}}$ ${\displaystyle \Rightarrow ^{*}}$ ${\displaystyle \Rightarrow }$

文法Gの言語は、その開始記号から導出可能なすべての終端記号文字列の集合であり、正式には： である。終端記号のみで構成される文字列で終わらない導出も可能であるが、 L ( G )には寄与しない。 ${\displaystyle L(G)=\{w\in \Sigma ^{*}\mid S\Rightarrow ^{*}w\}}$

文脈依存文法

形式文法が文脈依存的であるとは、 Pの各規則が空文字列である形式か、 ${\displaystyle S\to \varepsilon }$ ${\displaystyle \varepsilon }$

α A β → αγβ

ただし、A∈N、 [注^1] 、^[注2]、[^注3] ${\displaystyle \alpha ,\beta \in (N\cup \Sigma \setminus \{S\})^{*}}$ ${\displaystyle \gamma \in (N\cup \Sigma \setminus \{S\})^{+}}$

文脈依存文法という名称は、 Aの文脈を形成し、 Aがγに置き換えられるかどうかを決定するαとβによって説明されます。対照的に、文脈自由文法では文脈は存在しません。つまり、すべての生成規則の左辺は非終端記号です。

文字列γは空であってはならない。この制限がなければ、結果として得られる文法は制限のない文法と同等の性能となる。^[10]

（弱く）同等の定義

非縮約文法は、 u → vという形式の任意の生成規則に対して、 uの長さがvの長さ以下となる文法です。

すべての文脈依存文法は非縮約的であり、すべての非縮約的文法は同等の文脈依存文法に変換することができる。つまり、この2つのクラスは弱同等である。^[12]

一部の著者は、非縮約文法全般を指すために文脈依存文法という用語を使用しています。

左文脈依存文法と右文脈依存文法は、それぞれ規則をα A → αγとA β → γβの形式のみに制限することによって定義されます。これらの文法によって生成される言語は、文脈依存言語の完全なクラスでもあります。^{[13]この同値性は}ペントネン正規形によって確立されました。^[14]

例

a ⁿ b ⁿ c ⁿ

開始記号Sを持つ次の文脈依存文法は、標準的な非文脈自由言語{ a ⁿ b ⁿ c ⁿ | n ≥ 1}を生成する: ^{[引用が必要]}

1.		S	→	1つの	B	C
2.		S	→	1つの	S	B	C
3.	C	B	→	C	Z
4.	C	Z	→	W	Z
5.	W	Z	→	W	C
6.	W	C	→	B	C
7.	1つの	B	→	1つの	b
8.	b	B	→	b	b
9.	b	C	→	b	c
10.	c	C	→	c	c

^{ルール1と2は、} Sをn BC ( BC ) ^{n −1}に爆発させることを可能にします。ルール3から6は、各CBをBCに連続的に交換することを可能にします（ルールCB → BCはスキームαAβ →αγβに適合しないため、これには4つのルールが必要です）。ルール7–10は、適切な場所にある限り、非終端BまたはCをそれぞれ対応する終端bまたはcに置き換えることを可能にします。aaabbbcccの生成チェーンは次のとおりです。

S

→ ₂ aSBC

→ ₂ a aSBC BC

→ ₁ aa aBC BCBC

→ ₃ aaaB CZ CBC

→ ₄ aaaB WZ CBC

→ ₅ aaaB WC CBC

→ ₆ aaaB BC CBC

→ ₃ aaaBBC CZ C

→ ₄ aaaBBC WZ C

→ ₅ aaaBBC WC C

→ ₆ aaaBBC BC C

→ ₃ aaaBB CZ CC

→ ₄ aaaBB WZ CC

→ ₅ aaaBB WC CC

→ ₆ aaaBB BC CC

→ ₇ aa ab BBCCC

→ ₈ aaa bb BCCC

→ ₈ aaab bb CCC

→ ₉ aaabb bc CC

→ ₁₀ aaabb cc C

→ ₁₀ aaabbbc cc

a ⁿ b ⁿ c ⁿ d ⁿなど

より複雑な文法は、{ a ⁿ b ⁿ c ⁿ d ⁿ | n ≥ 1 }や、さらに多くの文字を含む他の言語を解析するために使用できます。ここでは、非縮約文法を用いたより単純な アプローチを 示します。 ^[要出典]文形式を 生成する通常の 生成規則のカーネルから始め、次に非縮約生成規則、、、、、、、、、、、を追加 します。 ${\displaystyle (ABCD)^{n}abcd}$ ${\displaystyle p_{Da}:Da\rightarrow aD}$ ${\displaystyle p_{Db}:Db\rightarrow bD}$ ${\displaystyle p_{Dc}:Dc\rightarrow cD}$ ${\displaystyle p_{Dd}:Dd\rightarrow dd}$ ${\displaystyle p_{Ca}:Ca\rightarrow aC}$ ${\displaystyle p_{Cb}:Cb\rightarrow bC}$ ${\displaystyle p_{Cc}:Cc\rightarrow cc}$ ${\displaystyle p_{Ba}:Ba\rightarrow aB}$ ${\displaystyle p_{Bb}:Bb\rightarrow bb}$ ${\displaystyle p_{Aa}:Aa\rightarrow aa}$

a ^m b ⁿ c ^m d ⁿ

この言語の非縮約文法（同等のCSGが存在する）は次のように定義される。 ${\displaystyle L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}\mid m\geq 1,n\geq 1\}}$

${\displaystyle p_{0}:S\rightarrow RT}$、

${\displaystyle p_{1}:R\rightarrow aRC|aC}$、

${\displaystyle p_{3}:T\rightarrow BTd|Bd}$、

${\displaystyle p_{5}:CB\rightarrow BC}$、

${\displaystyle p_{6}:aB\rightarrow ab}$、

${\displaystyle p_{7}:bB\rightarrow bb}$、

${\displaystyle p_{8}:Cd\rightarrow cd}$、 そして

${\displaystyle p_{9}:Cc\rightarrow cc}$。

これらの定義を用いると、 の導出は次のようになる。^[要出典] ${\displaystyle a^{3}b^{2}c^{3}d^{2}}$ ${\displaystyle S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}}$

1つの^{2 i}

言語{ a ^{2 i} | i ≥ 1}の非縮約文法は、(Hopcroft, Ullman, 1979)の例9.5(p. 224)で構築されている: ^[15]

1. ${\displaystyle S\rightarrow [ACaB]}$
2. ${\displaystyle {\begin{cases}\ [Ca]a\rightarrow aa[Ca]\\\ [Ca][aB]\rightarrow aa[CaB]\\\ [ACa]a\rightarrow [Aa]a[Ca]\\\ [ACa][aB]\rightarrow [Aa]a[CaB]\\\ [ACaB]\rightarrow [Aa][aCB]\\\ [CaB]\rightarrow a[aCB]\end{cases}}}$
3. ${\displaystyle [aCB]\rightarrow [aDB]}$
4. ${\displaystyle [aCB]\rightarrow [aE]}$
5. ${\displaystyle {\begin{cases}\ a[Da]\rightarrow [Da]a\\\ [aDB]\rightarrow [DaB]\\\ [Aa][Da]\rightarrow [ADa]a\\\ a[DaB]\rightarrow [Da][aB]\\\ [Aa][DaB]\rightarrow [ADa][aB]\end{cases}}}$
6. ${\displaystyle [ADa]\rightarrow [ACa]}$
7. ${\displaystyle {\begin{cases}\ a[Ea]\rightarrow [Ea]a\\\ [aE]\rightarrow [Ea]\\\ [Aa][Ea]\rightarrow [AEa]a\end{cases}}}$
8. ${\displaystyle [AEa]\rightarrow a}$

黒田正規形

空文字列を生成しない文脈依存文法はすべて、黒田正規形の弱同値文法に変換できる。ここでの「弱同値」とは、2つの文法が同じ言語を生成することを意味する。正規形は一般に文脈依存ではなく、非縮約文法となる。^{[16] [17]}

黒田正規形は、非縮約文法の実際の正規形です。

特性と用途

線形有界オートマトンとの同値性

形式言語は、文脈依存文法で記述できるのは、それが何らかの線形有界オートマトン（LBA）によって受理される場合のみである。^{[18]いくつかの教科書では、この結果は Landweber と}Kurodaのみに帰せられている。^[7]他の教科書では、これはMyhill -Landweber-Kuroda 定理と呼ばれている。^[19]（Myhill は 1960 年に決定性 LBA の概念を導入した。Peter S. Landweber は 1963 年に、決定性 LBA によって受理される言語は文脈依存であると発表しました。^[20] Kuroda は 1964 年に非決定性 LBA の概念と、LBA と CSG の同値性を導入しました。 ^{[21] [22]}）

2010年現在^{[更新が必要] 、すべての文脈依存言語が}決定論的LBAに受け入れられるかどうかは未解決の問題である。^[23][update]

閉鎖特性

文脈依存言語は補集合に関して閉じている。この1988年の結果は、イマーマン・シェレプセニの定理として知られている。^{[19]さらに、}和集合、積集合、連結、置換、^[注4] 逆準同型、クリーネプラスに関して閉じている。^[24]

任意の再帰的可算言語 Lは、ある文脈依存言語Lとある文字列準同型hに対してh ( L )と書くことができる。^[25]

計算上の問題

ある文字列s が文脈依存文法Gの言語に属するかどうかを問う決定問題は、PSPACE完全である。さらに、PSPACE完全である言語を持つ文脈依存文法も存在する。言い換えれば、ある文字列s がGの言語に属するかどうかを判定することがPSPACE完全であるような文脈依存文法G が存在する（したがって、 Gは固定されており、 sのみが問題の入力となる）。^[26]

文脈依存文法の空性問題（文脈依存文法Gが与えられたとき、L ( G )=∅か？）は決定不可能である。^{[27] [注5]}

自然言語のモデルとして

サヴィッチは、自然言語の基礎としてのCSGに対する批判の根拠となる以下の理論的結果を証明した。すなわち、任意の再帰的に可算な集合Rに対して、文脈依存言語/文法Gが存在し、これを次のようにRへの所属をテストするためのプロキシとして使用できる。すなわち、文字列sが与えられたとき、sがRに含まれるのは、 sc ⁿがGに含まれる正の整数nが存在する場合のみである。ここでcはRに含まれない任意の記号である。^[10]

ほぼすべての自然言語は一般に文脈依存文法によって特徴付けられることが示されているが、CSG のクラス全体は自然言語よりもはるかに大きいようだ。 ^{[引用が必要]さらに悪いことに、前述の CSG の決定問題は PSPACE 完全であるため、PSPACE 完全問題に対する多項式時間アルゴリズムは}P=NP を意味するため、CSG は実用的にはまったく機能しない。

一部の自然言語は文脈自由ではないことが、いわゆるクロスシリアル依存性と無制限スクランブル現象の特定に基づいて証明されている。^[要出典]しかし、これは必ずしもCSGのクラスが自然言語における日常的な意味での「文脈感受性」を捉えるために必要であることを意味するわけではない。例えば、線形文脈自由書き換えシステム（LCFRS）はCSGよりも厳密に弱いが、クロスシリアル依存性の現象を説明することができる。例えば、 { a ⁿ b ⁿ c ⁿ d ⁿ | n ≥ 1}に対してLCFRS文法を記述することができる。 ^{[28] [29] [30]}

計算言語学における継続的な研究は、木結合文法、組合せ範疇文法、結合文脈自由言語、線形文脈自由書き換えシステムなど、決定問題が実行可能な「軽度文脈依存」な言語のクラスを定式化することに焦点を当てています。これらの形式主義によって生成される言語は、文脈自由言語と文脈依存言語の中間に位置します。

最近では、 PTIMEクラスは範囲連結文法と同一視され、現在では軽度文脈依存言語クラスの中で最も表現力豊かなものと考えられています。^[30]

参照

• チョムスキー階層
• 文脈依存文法の発展
• 定節文法#非文脈自由文法
• 文脈依存文法のパーサージェネレーターのリスト

注記

1. すなわち、 Aは単一の非終端記号
2. すなわち、αとβの非終端記号（開始記号を除く）と終端記号の文字列
3. つまり、γは非終端記号（開始記号を除く）と終端記号の空でない文字列である。
4. より正式には、 L ⊆ Σ ^*が文脈依存言語であり、 f が各a ∈Σ を文脈依存言語f ( a ) に写像する場合、 f ( L ) もまた文脈依存言語である。
5. これは、(1)文脈自由言語は文脈依存言語でもあること、(2)文脈依存言語は積集合に関して閉じているが、(3)文脈自由言語の素性は決定不可能であることからも導かれる。

参考文献

1. (ホップクロフト、ウルマン、1979); セクション9.4、p.227
2. リンツ、ピーター (2011). 『形式言語とオートマトン入門』ジョーンズ＆バートレット出版社. p. 291. ISBN 978-1-4496-1552-9。
3. メドゥナ、アレクサンダー(2000). 『オートマトンと言語：理論と応用』 シュプリンガー・サイエンス＆ビジネス・メディア. p. 730. ISBN 978-1-85233-074-3。
4. デイビス, マーティン; シガル, ロン;ワイユカー, エレイン・J. (1994). 計算可能性、複雑性、そして言語：理論計算機科学の基礎（第2版）. モーガン・カウフマン. p. 189. ISBN 978-0-08-050246-5。
5. マーティン、ジョン・C. (2010).言語と計算理論入門（第4版）. ニューヨーク：マグロウヒル. p. 277. ISBN 9780073191461。
6. Levelt, Willem JM (2008). 『形式言語とオートマトン理論入門』John Benjamins Publishing. p. 26. ISBN 978-90-272-3250-2。
7. デイビス, マーティン; シガル, ロン;ワイユカー, エレイン J. (1994). 計算可能性, 複雑性, 言語: 理論計算機科学の基礎 (第2版). モーガン・カウフマン. pp.  330– 331. ISBN 978-0-08-050246-5。
8. Chomsky, N. (1963). 「文法の形式的性質」. Luce, RD; Bush, RR; Galanter, E. (編).数学心理学ハンドブック. ニューヨーク: Wiley. pp.  360– 363.
9. Levelt, Willem JM (2008). 『形式言語とオートマトン理論入門』John Benjamins Publishing. pp.  125– 126. ISBN 978-90-272-3250-2。
10. カルロス・マルティン・ヴィデ編 (1999). 数学言語学の諸問題：数学言語学に関するワークショップ、ペンシルベニア州ステートカレッジ、1998年4月. ジョン・ベンジャミンズ出版. pp.  186– 187. ISBN 90-272-1556-1。
11. Zhang, Da-Qian, Kang Zhang, Jiannong Cao. 「視覚言語の仕様記述のための文脈依存グラフ文法形式主義」『コンピュータジャーナル』 44.3 (2001): 186–200.
12. ホップクロフト, ジョン・E. ;ウルマン, ジェフリー・D. (1979). 『オートマトン理論、言語、計算入門』アディソン・ウェズレー. ISBN 9780201029888。; p. 223–224; 演習9、p. 230。2003年版では、CSGに関する章が省略されています。
13. ヘイズウィンケル、ミシェル(1989)。数学百科事典。 Vol. 4. シュプリンガーの科学とビジネスメディア。 p. 297.ISBN​ 978-1-55608-003-6。https://www.encyclopediaofmath.org/index.php/Grammar,_context-sensitive でもご覧いただけます。
14. 伊藤正美;小林裕司;庄司邦隆（2010）．オートマトン、形式言語、代数システム: AFLAS 2008 議事録、京都、日本、2008 年 9 月 20 ～ 22 日。World Scientific。 p. 183.ISBN​ 978-981-4317-60-3。ペントネン、マルッティ（1974年8月）「形式文法における片側文脈と両側文脈」を引用。情報制御誌25 ( 4): 371– 392. doi : 10.1016/S0019-9958(74)91049-3 .
15. 彼らは、例9.4に示されている無制限の文法を体系的に変換することによって文法を獲得しました。
    1. ${\displaystyle S\rightarrow ACaB}$、
    2. ${\displaystyle Ca\rightarrow aaC}$、
    3. ${\displaystyle CB\rightarrow DB}$、
    4. ${\displaystyle CB\rightarrow E}$、
    5. ${\displaystyle aD\rightarrow Da}$、
    6. ${\displaystyle AD\rightarrow AC}$、
    7. ${\displaystyle aE\rightarrow Ea}$、
    8. ${\displaystyle AE\rightarrow \varepsilon }$。
    文脈依存文法では、 のように角括弧で囲まれた文字列は単一の記号とみなされます（例えば、バッカス・ナウア記法のと同様です）。記号名は、非制限文法に類似するように選択されます。同様に、文脈依存文法における規則グループは、その元となった非制限文法規則に基づいて番号が付けられます。 ${\displaystyle [ACaB]}$<name-part>
16. 黒田重幸（1964年6月）「言語クラスと線形有界オートマトン」情報制御誌7 (2): 207– 223. doi : 10.1016/s0019-9958(64)90120-2 .
17. マテスク、アレクサンドル;サロマー、アルト(1997)。 「第 4 章: 古典言語理論の側面」。 Rozenberg , グジェグシュルツ;サロマー、アルト(編)。形式言語のハンドブック。第 1 巻: 単語、言語、文法。スプリンガー・フェルラーク。175 ～ 252ページ 。ISBN 3-540-61486-9。, ここで: 定理2.2、p. 190
18. (ホップクロフト、ウルマン、1979); 定理9.5、9.6、p.225–226
19. Sutner, Klaus (2016年春). 「文脈依存文法」(PDF) .カーネギーメロン大学. 2017年2月3日時点のオリジナル(PDF)からアーカイブ。 2019年8月29日閲覧。
20. PS Landweber (1963). 「タイプ1の句構造文法に関する3つの定理」.情報制御. 6 (2): 131– 136. doi : 10.1016/s0019-9958(63)90169-4 .
21. メドゥナ、アレクサンダー(2000). 『オートマトンと言語：理論と応用』 シュプリンガー・サイエンス＆ビジネス・メディア. p. 755. ISBN 978-1-85233-074-3。
22. Levelt, Willem JM (2008). 『形式言語とオートマトン理論入門』John Benjamins Publishing. pp.  126– 127. ISBN 978-90-272-3250-2。
23. マーティン、ジョン・C. (2010).言語と計算理論入門（第4版）. ニューヨーク：マグロウヒル. p. 283. ISBN 9780073191461。
24. (ホップクロフト、ウルマン、1979); 演習S9.10、p.230–231
25. (Hopcroft, Ullman, 1979); 演習 S9.14、p. 230–232。hは各シンボルをそれ自身または空の文字列にマッピングします。
26. QSAT問題を解くために設計されたそのような文法の例は、Lita, CV (2016-09-01). "On Complexity of the Detection Problem for Bounded Length Polymorphic Viruses". 2016 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC) . pp.  371– 378. doi :10.1109/SYNASC.2016.064. ISBNに掲載されています。 978-1-5090-5707-8. S2CID  18067130。
27. (ホップクロフト、ウルマン、1979); 演習S9.13、p.230–231
28. Kallmeyer, Laura (2011). 「軽度文脈依存文法形式論：自然言語は文脈自由ではない」（PDF） 。 2014年8月19日時点のオリジナルよりアーカイブ（PDF） 。
29. Kallmeyer, Laura (2011). 「Mildly Context-Sensitive Grammar Formalisms: Linear Context-Free Rewriting Systems」(PDF) . 2014年8月19日時点のオリジナルよりアーカイブ(PDF) 。
30. Kallmeyer, Laura (2010). Parsing Beyond Context-Free Grammars . Springer Science & Business Media. pp.  1– 5. ISBN 978-3-642-14846-0。

さらに読む

• メドゥナ、アレクサンダー、シュヴェツ、マーティン (2005).文脈条件付き文法とその応用. ジョン・ワイリー・アンド・サンズ. ISBN 978-0-471-73655-4。

外部リンク

• 文脈依存文法のためのEarley構文解析

Retrieved from "https://en.wikipedia.org/w/index.php?title=Context-sensitive_grammar&oldid=1253959429"