チョムスキー階層
つまり必ず「終端・非終端」か、必ず「非終端・終端」)。 S {\displaystyle S} が生成規則の右側に現れない場合、 S → ε {\displaystyle S\rightarrow \epsilon } という規則が存在しても良い。この文法で生成される言語群は有限オートマトンで判定可能である。さらにこのタイプの形式言語は正規表現として使用されている。正規言語は検索パターンの定義やプログラミング言語の字句構造に一般的に使われている。
帰納言語に対応する文法がこの階層のメンバーではないことに注意されたい。
正規言語は全て文脈自由言語に含まれ、文脈自由言語は全て文脈依存言語に含まれ、文脈依存言語は全て帰納言語に含まれ、帰納言語は全て帰納的可算言語に含まれる。これは正当な包含関係である(つまり、各タイプは上位タイプの真部分集合である)。したがって帰納言語ではない帰納的可算言語があり、文脈依存言語ではない帰納言語があり、文脈自由言語ではない文脈依存言語があり、正規言語ではない文脈自由言語がある。
以下の表はチョムスキーの四種類の文法をまとめたものであり、各クラスの生成する言語、それを認識するオートマトン、生成規則の制限を記している。