文脈依存的な言語

形式言語理論において、文脈依存言語とは、文脈依存文法によって定義できる形式言語であり、生成規則の適用可能性が記号の周囲の文脈に依存する場合がある。文脈に関係なく規則を適用できる文脈自由文法とは異なり、文脈依存文法では、特定の隣接記号が存在する場合にのみ規則を適用できるため、文字列の離れた部分間の依存関係や一致関係を表現できる。

これらの言語はチョムスキー階層のタイプ1言語に対応し、非縮約文法（生成規則によって文字列の全長が減少することのない文法）によって等価に定義されます。文脈依存言語は、主語と動詞の一致、クロスシリアル依存関係、その他のより単純な文法タイプでは捉えられない複雑な構文関係など、自然言語の現象をモデル化できるため、計算言語学や自然言語処理において重要です。

計算論的には、文脈依存言語は線形限定非決定性チューリングマシン（線形限定オートマトンとも呼ばれる）と同等である。つまり、テープ長がわずかである非決定性チューリングマシンである。${\displaystyle kn}$細胞では${\displaystyle n}$は入力のサイズであり、${\displaystyle k}$は、その機械に関連付けられた定数です。これは、そのような機械によって判定可能なすべての形式言語は文脈依存言語であり、すべての文脈依存言語はそのような機械によって判定可能であることを意味します。

この言語群は、非決定性チューリングマシン上の線形空間を使用して受理できるため、 NLINSPACE または NSPACE( O ( n )) とも呼ばれます。 ^{[ 1 ]} クラス LINSPACE (または DSPACE( O ( n ))) は、決定性チューリングマシンを使用する点を除いて、同じように定義されます。明らかに LINSPACE は NLINSPACE の部分集合ですが、LINSPACE = NLINSPACE かどうかはわかりません。^{[ 2 ]}

文脈依存だが文脈自由ではない言語の中で最も単純なものの一つは${\displaystyle L=\{a^{n}b^{n}c^{n}:n\geq 1\}}$:記号「a」が n 回、次に「b」がn回、次に「c」がn回出現するすべての文字列の言語(abc、 aabbcc、aaabbbcccなど)。この言語のスーパーセットであるバッハ言語^{[ 3 ]}は、「a」、「b」、「c」（または他の 3 つの記号のセット）が等しい頻度で出現し ( aabccb、baabcaccbなど)、かつ文脈依存であるすべての文字列の集合として定義されます。^{[ 4 ] [ 5 ]}

L が文脈依存言語であることは、Lを受理する線形限定オートマトンを構築することで示すことができる。また、各言語クラスに対応するポンピング補題をLに適用することで、L が正規言語でも文脈自由言語でもないことを容易に示すことができる。

同様に：

${\displaystyle L_{\textit {Cross}}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}}$は別の文脈依存言語です。対応する文脈依存文法は、次の形式で文形式を生成する 2 つの文脈自由文法から始めて簡単に投影できます。 ${\displaystyle a^{m}C^{m}}$ そして ${\displaystyle B^{n}d^{n}}$ そして、次のような順列生成法でそれらを補完する。 ${\displaystyle CB\rightarrow BC}$、新しい開始記号と標準的な構文糖。

${\displaystyle L_{MUL3}=\{a^{m}b^{n}c^{mn}:m\geq 1,n\geq 1\}}$これは別の文脈依存言語です（この言語の名前にある「3」は三進アルファベットを意味します）。つまり、「積」演算は文脈依存言語を定義します（ただし、「和」は文法として文脈自由言語のみを定義します）。${\displaystyle S\rightarrow aSc|R}$そして${\displaystyle R\rightarrow bRc|bc}$（図に示す）。積の可換性により、最も直感的な文法は${\displaystyle L_{\textit {MUL3}}}$曖昧です。この問題は、言語の定義をもう少し制限的にすることで回避できます。例えば、${\displaystyle L_{\textit {ORDMUL3}}=\{a^{m}b^{n}c^{mn}:1<m<n\}}$これは、 ${\displaystyle L_{\textit {MUL1}}=\{a^{mn}:m>1,n>1\}}$そして、このことから、${\displaystyle L_{m^{2}}=\{a^{m^{2}}:m>1\}}$、${\displaystyle L_{m^{3}}=\{a^{m^{3}}:m>1\}}$など

${\displaystyle L_{REP}=\{w^{|w|}:w\in \Sigma ^{*}\}}$は文脈依存言語である。対応する文脈依存文法は、 の文脈依存文法の一般化として得られる。${\displaystyle L_{\textit {Square}}=\{w^{2}:w\in \Sigma ^{*}\}}$、${\displaystyle L_{\textit {Cube}}=\{w^{3}:w\in \Sigma ^{*}\}}$など

${\displaystyle L_{\textit {EXP}}=\{a^{2^{n}}:n\geq 1\}}$は文脈依存言語である。^{[ 6 ]}

${\displaystyle L_{\textit {PRIMES2}}=\{w:|w|{\mbox{ is prime }}\}}$これは文脈依存言語です（この言語の名前にある「2」は二進アルファベットを意味します）。これは、Hartmanis が二進アルファベット上の正規言語と文脈自由言語のポンピング補題を使用して証明し、その後、線形有界マルチテープオートマトンを受理する概略図を作成しました。${\displaystyle L_{PRIMES2}}$[ ^{7 ]​}

${\displaystyle L_{\textit {PRIMES1}}=\{a^{p}:p{\mbox{ is prime }}\}}$これは文脈依存言語です（この言語の名前にある「1」は単項アルファベットを意味します）。これは、A. Salomaa が単項アルファベット上の線形限定オートマトンによって Matti Soittola に帰属させ、^{また同じく単項}アルファベット上の文脈依存文法によって Marti Penttonen にも帰属させています（A. Salomaa 著『形式言語』14 ページ、例 2.5 を参照）。

文脈に依存しない再帰言語の例としては、例えばべき乗を含む同等の正規表現のペアの集合のように、決定がEXPSPACE困難問題となるような再帰言語が挙げられる。

• 2 つの文脈依存言語の和集合、積集合、連結は文脈依存であり、文脈依存言語のクリーネプラスも文脈依存である。 ^{[ 9 ]}
• 文脈依存言語の補語自体も文脈依存的である^{[ 10 ]。}これはイマーマン・セレプセニの定理として知られる結果である。
• 任意の文脈依存文法、または任意の決定論的文脈依存文法によって定義された言語に文字列が属するかどうかを判定する問題は、PSPACE完全問題である。

• 文脈依存言語用のパーサー生成器一覧
• インデックス言語– 文脈依存言語の厳密なサブセット
• 堰の階層構造
• 軽度文脈依存文法形式体系― 文脈依存言語の様々な下位クラスのための形式体系の集合

• Sipser, M. (1996), Introduction to the Theory of Computation , PWS Publishing Co.