Classificazione di Chomsky delle grammatiche

Secondo Noam Chomosky, ci sono quattro tipi di grammatiche: Tipo 0, Tipo 1, Tipo 2 e Tipo 3. La tabella seguente mostra come differiscono l'una dall'altra -

Tipo di grammatica	Grammatica accettata	Lingua accettata	Automa
Digita 0	Grammatica illimitata	Linguaggio ricorsivamente enumerabile	Macchina di Turing
Tipo 1	Grammatica sensibile al contesto	Linguaggio sensibile al contesto	Automa lineare limitato
Tipo 2	Grammatica senza contesto	Linguaggio senza contesto	Automa a spinta
Tipo 3	Grammatica regolare	Linguaggio regolare	Automa a stati finiti

Dai un'occhiata alla seguente illustrazione. Mostra l'ambito di ogni tipo di grammatica -

Tipo - 3 grammatica

Type-3 grammarsgenerare linguaggi regolari. Le grammatiche di tipo 3 devono avere un singolo non terminale sul lato sinistro e un lato destro costituito da un singolo terminale o singolo terminale seguito da un singolo non terminale.

Le produzioni devono essere nella forma X → a or X → aY

dove X, Y ∈ N (Non terminale)

e a ∈ T (Terminale)

La regola S → ε è consentito se S non appare a destra di nessuna regola.

Esempio

X → ε 
X → a | aY
Y → b

Tipo - 2 grammatica

Type-2 grammars generare linguaggi privi di contesto.

Le produzioni devono essere nella forma A → γ

dove A ∈ N (Non terminale)

e γ ∈ (T ∪ N)* (Stringa di terminali e non terminali).

Questi linguaggi generati da queste grammatiche sono riconosciuti da un automa pushdown non deterministico.

Esempio

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

Tipo - 1 grammatica

Type-1 grammarsgenerare linguaggi sensibili al contesto. Le produzioni devono essere nella forma

α A β → α γ β

dove A ∈ N (Non terminale)

e α, β, γ ∈ (T ∪ N)* (Stringhe di terminali e non terminali)

Le corde α e β potrebbe essere vuoto, ma γ non deve essere vuoto.

La regola S → εè consentito se S non compare a destra di nessuna regola. I linguaggi generati da queste grammatiche sono riconosciuti da un automa lineare limitato.

Esempio

AB → AbBc 
A → bcA 
B → b

Tipo - 0 grammatica

Type-0 grammarsgenerare linguaggi enumerabili ricorsivamente. Le produzioni non hanno restrizioni. Sono qualsiasi grammatica a struttura di fase, comprese tutte le grammatiche formali.

Generano i linguaggi riconosciuti da una macchina di Turing.

Le produzioni possono essere sotto forma di α → β dove α è una stringa di terminali e non terminali con almeno un non terminale e α non può essere nullo. β è una stringa di terminali e non terminali.

Esempio

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