チョムスキー階層

タイプ3文法は正規言語を生成します。このような文法は、左辺に単一の非終端記号、右辺に単一の終端記号（場合によっては単一の非終端記号が続く）を持つ規則に限定します。この場合、文法は右正規です。あるいは、すべての規則の右辺が単一の終端記号（場合によっては単一の非終端記号が先行する）で構成される場合もあります（左正規）。これらは同じ言語を生成します。ただし、左正規規則と右正規規則を組み合わせると、言語は正規である必要がなくなります。規則${\displaystyle S\rightarrow \varepsilon }$ここでも許可されています。${\displaystyle S}$どのルールの右側にも現れません。これらの言語は、有限状態オートマトンによって判定可能なすべての言語です。さらに、この形式言語のファミリーは正規表現によって得られます。正規言語は、検索パターンやプログラミング言語の字句構造を定義するためによく使用されます。

例えば、通常の言語${\displaystyle L=\{a^{n}\mid n>0\}}$タイプ3文法によって生成されます${\displaystyle G=(\{S\},\{a\},P,S)}$制作と共に${\displaystyle P}$以下の通りである。

S → aS

S → a

言語学では、規則的でない言語は超規則言語と呼ばれる。^{[ 8 ] [ 9 ]}

タイプ2文法は文脈自由言語を生成する。これらは次の形式の規則によって定義される。${\displaystyle A\rightarrow \alpha }$と${\displaystyle A}$非終端であり、${\displaystyle \alpha }$終端記号および/または非終端記号の文字列である。これらの言語は、非決定性プッシュダウンオートマトンによって認識できるすべての言語である。文脈自由言語、あるいはむしろその部分集合である決定性文脈自由言語は、ほとんどのプログラミング言語の句構造の理論的基盤であるが、その意味解析には宣言とスコープによる文脈依存の名前解決が含まれる。多くの場合、 LL パーサーのように、構文解析を容易にするために文法の部分集合が使用される。

例えば、文脈自由言語 ${\displaystyle L=\{a^{n}b^{n}\mid n>0\}}$タイプ2文法によって生成されます${\displaystyle G=(\{S\},\{a,b\},P,S)}$制作と共に${\displaystyle P}$以下の通りである。

S → aSb

S → ab

この言語は文脈自由言語であるが、正規言語ではない（正規言語のポンピング補題による）。

あらゆる文脈自由言語は、チョムスキー標準形の文法によって生成できる。

タイプ1文法は文脈依存言語を生成する。これらの文法は、次の形式の規則を持つ。${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$と${\displaystyle A}$非終端および${\displaystyle \alpha }$、${\displaystyle \beta }$そして${\displaystyle \gamma }$終端記号および／または非終端記号の文字列。文字列${\displaystyle \alpha }$そして${\displaystyle \beta }$空かもしれませんが、${\displaystyle \gamma }$空であってはならない。ルール${\displaystyle S\rightarrow \epsilon }$許可されている場合${\displaystyle S}$どの規則の右側にも現れません。これらの文法で記述される言語は、線形限定オートマトン（入力の長さの定数倍でテープが制限される非決定性チューリングマシン）によって認識可能なすべての言語です。

例えば、文脈依存言語 ${\displaystyle L=\{a^{n}b^{n}c^{n}\mid n>0\}}$タイプ1文法によって生成されます${\displaystyle G=(\{S,A,B,C,W,Z\},\{a,b,c\},P,S)}$制作と共に${\displaystyle P}$以下の通りである。

S → aBC

S → aSBC

CB → CZ

CZ → WZ

WZ → WC

WC → BC

aB → ab

bB → bb

bC → bc

cC → cc

この言語は文脈依存的だが文脈自由ではない（文脈自由言語のポンピング補題による）。この文法が生成する証明${\displaystyle L=\{a^{n}b^{n}c^{n}\mid n>0\}}$文脈依存文法に関する記事で概説されています。

タイプ 0 文法には、すべての形式文法が含まれます。生成規則には制約がありません。タイプ 0 文法は、チューリング マシンで認識できるすべての言語を正確に生成するため、生成可能な言語はすべてタイプ 0 文法で生成できます。^{[ 10 ]}これらの言語は、再帰的に列挙可能な言語またはチューリング認識可能な言語としても知られています。 ^{[ 10 ]}これは、常に停止するチューリング マシンで判定できる再帰言語とは異なることに注意してください。