Classification de Chomsky des grammaires

Selon Noam Chomosky, il existe quatre types de grammaires - Type 0, Type 1, Type 2 et Type 3. Le tableau suivant montre en quoi elles diffèrent les unes des autres -

Type de grammaire	Grammaire acceptée	Langue acceptée	Automate
Type 0	Grammaire illimitée	Langage récursivement énumérable	Machine de Turing
Type 1	Grammaire contextuelle	Langage contextuel	Automate à délimitation linéaire
Type 2	Grammaire sans contexte	Langage sans contexte	Automate pushdown
Type 3	Grammaire régulière	Langue ordinaire	Automate à états finis

Jetez un œil à l'illustration suivante. Il montre la portée de chaque type de grammaire -

Type - 3 Grammaire

Type-3 grammarsgénérer des langues régulières. Les grammaires de type 3 doivent avoir un seul non-terminal sur le côté gauche et un côté droit constitué d'un seul terminal ou d'un seul terminal suivi d'un seul non-terminal.

Les productions doivent être de la forme X → a or X → aY

où X, Y ∈ N (Non terminal)

et a ∈ T (Terminal)

La règle S → ε est autorisé si S n'apparaît à droite d'aucune règle.

Exemple

X → ε 
X → a | aY
Y → b

Type - 2 Grammaire

Type-2 grammars générer des langages sans contexte.

Les productions doivent être de la forme A → γ

où A ∈ N (Non terminal)

et γ ∈ (T ∪ N)* (Chaîne de terminaux et non terminaux).

Ces langages générés par ces grammaires sont reconnus par un automate pushdown non déterministe.

Exemple

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

Type - 1 Grammaire

Type-1 grammarsgénérer des langages contextuels. Les productions doivent être de la forme

α A β → α γ β

où A ∈ N (Non terminal)

et α, β, γ ∈ (T ∪ N)* (Chaînes de terminaux et non terminaux)

Les cordes α et β peut être vide, mais γ doit être non vide.

La règle S → εest autorisée si S n'apparaît sur le côté droit d'aucune règle. Les langages générés par ces grammaires sont reconnus par un automate linéaire borné.

Exemple

AB → AbBc 
A → bcA 
B → b

Type - 0 Grammaire

Type-0 grammarsgénérer des langues énumérables récursivement. Les productions n'ont aucune restriction. Il s'agit de toute grammaire à structure de phase comprenant toutes les grammaires formelles.

Ils génèrent les langages reconnus par une machine de Turing.

Les productions peuvent être sous la forme de α → β où α est une chaîne de terminaux et de non terminaux avec au moins un non terminal et α ne peut pas être nulle. β est une chaîne de terminaux et de non-terminaux.

Exemple

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