チョムスキー階層

出典: フリー百科事典『ウィキペディア（Wikipedia）』

チョムスキー階層（-かいそう、Chomsky Hierarchy）とは、形式言語を生成する形式文法のクラスの包含階層である。これは「句構造文法」（Phrase Structure Grammars）の階層とも呼ばれ、1956年にノーム・チョムスキーが発表した。

[編集] 形式文法

形式文法の構成要素は、「終端記号」（Terminal Symbols）の有限集合（形式言語の単語で使われる文字）、「非終端記号」（Nonterminal Symbols）の有限集合、「生成規則」（Production Rules）の有限集合（各生成規則は右側と左側に記号列で構成される単語を含む）、「開始記号」（Start Symbol）から構成される。生成規則はある単語に適用され、規則の左側にある単語を右側にある記号列で置換する。導出は一連の規則適用過程である。このような文法で開始記号から始めて生成規則を適用していくことによって終端記号のみから構成される単語を生成する。そのような単語全体の集合が形式言語である。

非終端記号は大文字、終端記号は小文字で表すことが多く、開始記号は $S$ で示される。例えば、終端記号 ${a, b}$ と非終端記号 ${S, A, B}$ から構成される文法の生成規則が以下のようなものであるとする。

S

→

A B S

S

→ ε (ここで ε は空の文字列)

B A

→

A B

B S

→

b

B b

→

b b

A b

→

a b

A a

→

a a

これにより開始記号 $S$ から定義される全単語で構成される言語は $a n b n$ である（ $n$ 個の $a$ の後に $n$ 個の $b$ が続く形式）。同様の言語をもっと単純な文法で定義した例を以下に示す。終端記号 ${p, q}$ 、非終端記号 ${S}$ 、開始記号 $S$ で生成規則は以下のようになる。

S

→

p S q

S

→ ε

詳しくは形式文法を参照されたい。

[編集] 階層

チョムスキー階層は以下のレベルから構成される。

タイプ-0 文法（制限のない文法）は全ての形式文法を包含する。この文法はチューリングマシンが認識できる全言語を生成できる。その言語群は帰納的可算言語（Recursively Enumerable Language）として知られている。これはチューリングマシンが必ず停止して判定可能な帰納言語（Recursive Language）とは異なる。

タイプ-1 文法（文脈依存文法）は文脈依存言語を生成する。この文法は $\alpha A\beta \rightarrow \alpha\gamma\beta$ という形式の生成規則を持ち、 $A$ は非終端記号、 $α$ と $β$ と $γ$ は終端記号と非終端記号から構成される文字列である。 $α$ と $β$ は空の文字列の場合もあるが、 $γ$ は空でない文字列でなければならない。 $S$ が生成規則の右側に現れない場合、 $S \rightarrow \epsilon$ という規則が存在しても良い。この文法によって記述される言語は線形拘束オートマトンで認識できる。

タイプ-2 文法（文脈自由文法）は文脈自由言語を生成する。この文法は $A \rightarrow \gamma$ という形式の生成規則を持ち、 $A$ は非終端記号、 $γ$ は終端記号と非終端記号から構成される文字列である。この文法で生成される言語群は非決定性プッシュダウン・オートマトンが認識できる言語である。文脈自由言語は多くのプログラミング言語の文法の理論的基盤となっている。

タイプ-3 文法（正規文法）は正規言語を生成する。この文法の生成規則は左側には必ずひとつの非終端記号があり、右側には必ずひとつの終端記号とひとつかゼロ個の非終端記号がある（順番はひとつの文法内では決められている。つまり必ず「終端・非終端」か、必ず「非終端・終端」）。 $S$ が生成規則の右側に現れない場合、 $S \rightarrow \epsilon$ という規則が存在しても良い。この文法で生成される言語群は有限オートマトンで判定可能である。さらにこのタイプの形式言語は正規表現として使用されている。正規言語は検索パターンの定義やプログラミング言語の字句構造に一般的に使われている。

帰納言語に対応する文法がこの階層のメンバーではないことに注意されたい。

正規言語は全て文脈自由言語に含まれ、文脈自由言語は全て文脈依存言語に含まれ、文脈依存言語は全て帰納言語に含まれ、帰納言語は全て帰納的可算言語に含まれる。これは正当な包含関係である（つまり、各タイプは上位タイプの真部分集合である）。したがって帰納言語ではない帰納的可算言語があり、文脈依存言語ではない帰納言語があり、文脈自由言語ではない文脈依存言語があり、正規言語ではない文脈自由言語がある。

以下の表はチョムスキーの四種類の文法をまとめたものであり、各クラスの生成する言語、それを認識するオートマトン、生成規則の制限を記している。

句構造文法階層	文法	言語	オートマトン	生成規則
タイプ-0	--	帰納的可算	チューリングマシン	制限なし
タイプ-1	文脈依存	文脈依存	線形拘束オートマトン	$\alpha A\beta \rightarrow \alpha\gamma\beta$
タイプ-2	文脈自由	文脈自由	プッシュダウン・オートマトン	$A \rightarrow \gamma$
タイプ-3	正規	正規	有限オートマトン	$A \rightarrow a$ および $A \rightarrow aB$ または $A \rightarrow Ba$