チョムスキー階層（チョムスキーかいそう、"Chomsky Hierarchy"）とは、形式言語を生成する形式文法のクラスの包含階層である。これは「句構造文法」（"Phrase Structure Grammars"）の階層とも呼ばれ、1956年にノーム・チョムスキーが発表した。形式文法の構成要素は、「終端記号」（"Terminal Symbols"）の有限集合（形式言語の単語で使われる文字）、「非終端記号」（"Nonterminal Symbols"）の有限集合、「生成規則」（"Production Rules"）の有限集合（各生成規則は右側と左側に記号列で構成される単語を含む）、「開始記号」（"Start Symbol"）から構成される。生成規則はある単語に適用され、規則の左側にある単語を右側にある記号列で置換する。導出は一連の規則適用過程である。このような文法で開始記号から始めて生成規則を適用していくことによって終端記号のみから構成される単語を生成する。そのような単語全体の集合が形式言語である。非終端記号は大文字、終端記号は小文字で表すことが多く、開始記号は formula_1 で示される。例えば、終端記号 formula_2 と非終端記号 formula_3 から構成される文法の生成規則が以下のようなものであるとする。これにより開始記号 formula_1 から定義される全単語で構成される言語は formula_13 である（formula_14 個の formula_15 の後に formula_14 個の formula_17 が続く形式）。同様の言語をもっと単純な文法で定義した例を以下に示す。終端記号 formula_18、非終端記号 formula_19、開始記号 formula_1 で生成規則は以下のようになる。チョムスキー階層は以下のレベルから構成される。帰納言語に対応する文法がこの階層のメンバーではないことに注意されたい。正規言語は全て文脈自由言語に含まれ、文脈自由言語は全て文脈依存言語に含まれ、文脈依存言語は全て帰納言語に含まれ、帰納言語は全て帰納的可算言語に含まれる。これは正当な包含関係である（つまり、各タイプは上位タイプの真部分集合である）。したがって帰納言語ではない帰納的可算言語があり、文脈依存言語ではない帰納言語があり、文脈自由言語ではない文脈依存言語があり、正規言語ではない文脈自由言語がある。以下の表はチョムスキーの四種類の文法をまとめたものであり、各クラスの生成する言語、それを認識するオートマトン、生成規則の制限を記している。

出典:wikipedia