文脈依存文法

形式文法を次のように表記します。${\displaystyle G=(N,\Sigma ,P,S)}$、 と${\displaystyle N}$非終端記号のセット、${\displaystyle \Sigma }$ターミナルシンボルのセット、${\displaystyle P}$一連の生産ルール、そして${\displaystyle S\in N}$スタートシンボル。

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

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

形式文法は、Pの各規則が次のいずれかの形式である場合に文脈依存的である。${\displaystyle S\to \varepsilon }$どこ${\displaystyle \varepsilon }$は空文字列、または次の形式です。

α A β → αγβ

A ∈ Nの場合、^{[注 1 ]}${\displaystyle \alpha ,\beta \in (N\cup \Sigma \setminus \{S\})^{*}}$[^{注2 ]}および$\displaystyle \gamma \in (N\cup \Sigma \setminus \{S\})^{+}}$[^{注3 ]}

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

文字列γは空であってはならない。この制約がない場合、結果として得られる文法は制約のない文法と同等の能力を持つことになる。^{[ 10 ]}

非収縮文法とは、 u → vの形式の任意の生成規則に対して、 uの長さがvの長さ以下である文法のことである。

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

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

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

開始記号Sを持つ以下の文脈依存文法は、標準的な非文脈自由言語{ a ⁿ b ⁿ c ⁿ | n ≥ 1 }を生成します 。

規則 1 と 2 はS をⁿ 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

→ ₁₀ aaabbb 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}$

形式言語は、線形限定オートマトン(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 ]}

文脈依存言語は補集合に関して閉じている。この 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 ]}

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

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

計算言語学における継続的な研究は、ツリー隣接文法、組み合わせカテゴリ文法、結合コンテキストフリー言語、線形コンテキストフリー書き換えシステムなど、決定問題が実行可能な「ややコンテキスト依存的」な言語クラスの定式化に焦点を当ててきた。これらの形式体系によって生成される言語は、コンテキストフリー言語とコンテキスト依存的言語の中間に位置する。

最近では、クラスPTIME は範囲連結文法と同一視されており、現在では軽度文脈依存言語クラスの中で最も表現力が高いと考えられている。^{[ 30 ]}