文脈依存文法

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

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

チョムスキーは、文脈に応じて単語が特定の場所で適切であったり不適切であったりすることが多い自然言語の構文を記述する方法として文脈依存文法を導入した。ウォルター・サヴィッチは「文脈依存」という用語は誤解を招くと批判し、CSGと無制限文法の違いをよりよく説明する「非消去」を提案した。^[10]

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

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

文字列は、 と表記される文字列を直接生成する、またはに直接導出するとは、P内の何らかの生成規則を適用してuからv を取得できる場合、つまり かつ である場合( は生成規則、 はそれぞれ文字列の影響を受けない左側と右側の部分) であると言います。より一般的には、 u は、 と表記される文字列vを生成する、またはに導出するとは、生成規則を繰り返し適用してuからvを取得できる場合、つまりのあるn ≥ 0 およびいくつかの文字列に対して である場合に言えます。言い換えると、関係 は関係 の反射的推移閉包です。 ${\displaystyle u\in (N\cup \Sigma )^{*}}$ ${\displaystyle v\in (N\cup \Sigma )^{*}}$${\displaystyle u\Rightarrow v}$${\displaystyle u=\ガンマ L\デルタ }$${\displaystyle v=\ガンマ R\デルタ }$${\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 \epsilon }$

α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]

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

ルール 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 SBC BC

→ ₁ aa aBC BCBC

→ ₃ aaaB CZ CBC

→ ₄ aaaB WZ CBC

→ ₅ aaaB WC CBC

→ ₆ aaaB BC CBC

→ ₃ aaaBBC CZ C

→ ₄ aaaBBC WZC​

→ ₅ aaaBBC WC C

→ ₆ aaaBBCBC​​

→ ₃ aaaBB CZ CC

→ ₄ aaaBB WZCC​

→ ₅ aaaBB WC CC

→ ₆ aaaBBBCCC​​

→ ₇ aa ab BBCCC

→ ₈ aaa bb BCCC

→ ₈ aaabbCCC​​

→ ₉ aaabb bc CC

→ ₁₀ cc C​

→ ₁₀ aaabbbc cc

より複雑な文法を使用して、{ 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}$

言語の非縮約文法（同等の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 }}$

言語{ 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]

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

• Meduna, Alexander ; Švec, Martin (2005)。文脈条件付き文法とその応用。John Wiley & Sons。ISBN 978-0-471-73655-4。

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