文法のチョムスキー分類

Noam Chomoskyによると、文法にはタイプ0、タイプ1、タイプ2、タイプ3の4種類があります。次の表に、それらの違いを示します。

文法タイプ	文法が受け入れられました	受け入れられる言語	オートマトン
タイプ0	無制限文法	帰納的可算言語	チューリングマシン
タイプ1	状況依存文法	状況依存言語	線形拘束オートマトン
タイプ2	文脈自由文法	文脈自由言語	プッシュダウンオートマトン
タイプ3	正規文法	正規言語	有限状態オートマトン

次の図を見てください。各タイプの文法の範囲を示しています-

タイプ-3文法

Type-3 grammars正規言語を生成します。タイプ3の文法では、左側に単一の非終端記号があり、右側に単一の終端記号または単一の終端記号とそれに続く単一の非終端記号が含まれている必要があります。

作品は形式でなければなりません X → a or X → aY

どこ X, Y ∈ N （非終端記号）

そして a ∈ T （ターミナル）

ルール S → ε 次の場合に許可されます S ルールの右側には表示されません。

例

X → ε 
X → a | aY
Y → b

タイプ-2文法

Type-2 grammars 文脈自由言語を生成します。

作品は形式でなければなりません A → γ

どこ A ∈ N （非終端記号）

そして γ ∈ (T ∪ N)* （終端記号と非終端記号の文字列）。

これらの文法によって生成されたこれらの言語は、非決定性プッシュダウンオートマトンによって認識されます。

例

S → X a 
X → a 
X → aX 
X → abc 
X → ε

タイプ-1文法

Type-1 grammars状況依存言語を生成します。作品は形式でなければなりません

α A β → α γ β

どこ A ∈ N （非終端記号）

そして α, β, γ ∈ (T ∪ N)* （終端記号と非終端記号の文字列）

弦 α そして β 空かもしれませんが γ 空でない必要があります。

ルール S → εSがどのルールの右側にも表示されない場合に許可されます。これらの文法によって生成された言語は、線形拘束オートマトンによって認識されます。

例

AB → AbBc 
A → bcA 
B → b

タイプ-0文法

Type-0 grammars帰納的可算言語を生成します。制作に制限はありません。それらは、すべての形式文法を含む任意の位相構造文法です。

それらはチューリングマシンによって認識される言語を生成します。

作品は次の形をとることができます α → β どこ α は、少なくとも1つの非終端記号と非終端記号を含む一連の終端記号と非終端記号です。 α nullにすることはできません。 β 終端記号と非終端記号の文字列です。

例

S → ACaB 
Bc → acB 
CB → DB 
aD → Db