Klasyfikacja gramatyki Chomsky'ego

Według Noama Chomosky'ego istnieją cztery typy gramatyki - typ 0, typ 1, typ 2 i typ 3. Poniższa tabela pokazuje, czym się one od siebie różnią -

Typ gramatyki	Zaakceptowano gramatykę	Zaakceptowano język	Automat
Wpisz 0	Nieograniczona gramatyka	Język rekurencyjnie wyliczalny	Maszyna Turinga
Typ 1	Gramatyka kontekstowa	Język wrażliwy na kontekst	Automat z ograniczeniami liniowymi
Wpisz 2	Gramatyka bezkontekstowa	Język bezkontekstowy	Automat dociskowy
Wpisz 3	Gramatyka regularna	Język zwykły	Automat skończony

Spójrz na poniższą ilustrację. Pokazuje zakres każdego rodzaju gramatyki -

Typ - 3 gramatyki

Type-3 grammarsgeneruj języki regularne. Gramatyki typu 3 muszą mieć pojedynczy terminal nieterminalny po lewej stronie i prawostronny składający się z pojedynczego terminala lub pojedynczego terminala, po którym następuje pojedynczy nieterminal.

Produkcje muszą być w formie X → a or X → aY

gdzie X, Y ∈ N (Bez terminala)

i a ∈ T (Terminal)

Zasada S → ε jest dozwolone, jeśli S nie pojawia się po prawej stronie żadnej reguły.

Przykład

X → ε 
X → a | aY
Y → b

Typ - 2 Gramatyka

Type-2 grammars generować języki bezkontekstowe.

Produkcje muszą być w formie A → γ

gdzie A ∈ N (Bez terminala)

i γ ∈ (T ∪ N)* (Ciąg terminali i nieterminali).

Te języki generowane przez te gramatyki są rozpoznawane przez niedeterministyczny automat ze stosem.

Przykład

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

Typ - 1 gramatyka

Type-1 grammarsgenerować języki kontekstowe. Produkcje muszą być w formie

α A β → α γ β

gdzie A ∈ N (Nieterminalowe)

i α, β, γ ∈ (T ∪ N)* (Ciągi terminali i nieterminali)

Sznurki α i β może być pusty, ale γ nie może być puste.

Zasada S → εjest dozwolone, jeśli S nie pojawia się po prawej stronie żadnej reguły. Języki generowane przez te gramatyki są rozpoznawane przez automat liniowo ograniczony.

Przykład

AB → AbBc 
A → bcA 
B → b

Typ - 0 Gramatyka

Type-0 grammarsgeneruje rekurencyjnie wyliczalne języki. Produkcje nie mają ograniczeń. Są to dowolne gramatyki struktur fazowych, w tym wszystkie gramatyki formalne.

Generują języki, które są rozpoznawane przez maszynę Turinga.

Produkcje mogą mieć postać α → β gdzie α jest ciągiem terminali i nieterminali z co najmniej jednym nieterminalnym i α nie może być zero. β jest ciągiem terminali i nieterminali.

Przykład

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