文脈依存文法

文脈依存文法の概要

文脈依存文法（Context-sensitive Grammar, CSG）は、形式文法の一種であり、生成規則が特定の条件に依存している点で特徴的です。この文法では、非終端記号はその周囲に位置する他の記号の文脈に応じて異なる形で変換されます。具体的には、文法Gは4つの要素から構成され、これらは非終端記号の集合N、終端記号の集合Σ、生成規則の集合P、初期非終端記号Sから成ります。生成規則は特に次の形状を取ります：

αAβ → αγβ

ここで、非終端記号AはNに属し、αとβは非終端記号と終端文字から構成される文字列を指します。また、γは空でない文字列であり、非終端記号と終端記号の任意の組み合わせから成り立っています。

文脈依存とその重要性

文脈依存文法の最大の特徴は、Aの前後に位置する文字列によって、その変換が可能か否かが決定されることにあります。このため、生成される言語は、文脈自由文法では捉えきれないような複雑な構造を持つことができます。文脈自由文法では、終端文字列の前後関係は考慮されず、一文字または一つの非終端記号だけが対象になるため、文脈依存文法が持つ柔軟性とは一線を画します。文脈依存文法の起源は1950年代にさかのぼり、ノーム・チョムスキーによって導入されました。彼は自然言語の文法構造の複雑さを捉えるために、この文法形式を提案したのです。

別の定義とその特性

文脈依存文法には、生成規則に対して制約を加えた別の定義も存在します。具体的には、次の制約が求められます：


すなわち、生成規則の左辺の長さが右辺の長さよりも短いことが必要です。この形式の文法は文字列の長さが減ることがないため、「単調文法」または「非縮小文法」とも呼ばれます。文脈依存文法と非縮小文法は異なりますが、ほぼ同等の言語クラスを定義することが可能です。特に、文脈依存文法は空文字列εを生成できますが、非縮小文法は生成することができません。

具体例

文脈依存文法の具体例として、以下の生成規則を挙げます：

S → aSBC | aBC
CB → HB
HB → HC
HC → BC
aB → ab
bB → bb
bC → bc
cC → cc

この文法によって生成される言語は次のような形式になります：

{ a^n b^n c^n : n ≥ 1 }

この言語は文脈自由言語ではないため、文脈依存文法の特性が活かされています。文脈依存文法においては、生成規則が複数の文字に対して適用されることが許され、その際に長さに関する制約が存在しないのが特徴です。文脈自由文法では一文字に対してのみ操作が行われるため、生成される言語の構造に限界があります。

計算的特性

文脈依存文法に対する決定問題はPSPACE完全であり、計算を行う上での難易度が高いことを示しています。この種の文法の認識問題も同様にPSPACE完全であり、より複雑な言語の生成が可能であることを反映しています。

文脈依存文法は自然言語の理解や解析、計算機科学の理論と実用において重要な役割を果たしており、その特性を理解することは多くの分野において有意義です。

もう一度検索