Classificação Chomsky de Gramáticas

De acordo com Noam Chomosky, existem quatro tipos de gramáticas - Tipo 0, Tipo 1, Tipo 2 e Tipo 3. A tabela a seguir mostra como elas diferem umas das outras -

Tipo de Gramática	Grammar Accepted	Idioma aceito	Autômato
Tipo 0	Gramática irrestrita	Linguagem recursivamente enumerável	Máquina de Turing
Tipo 1	Gramática sensível ao contexto	Linguagem sensível ao contexto	Autômato linear
Tipo 2	Gramática livre de contexto	Linguagem livre de contexto	Autômato pushdown
Tipo 3	Gramática regular	Linguagem regular	Autômato de estado finito

Dê uma olhada na ilustração a seguir. Mostra o escopo de cada tipo de gramática -

Tipo - 3 gramática

Type-3 grammarsgerar linguagens regulares. As gramáticas do tipo 3 devem ter um único não terminal no lado esquerdo e um lado direito consistindo em um único terminal ou único terminal seguido por um único não terminal.

As produções devem estar no formato X → a or X → aY

Onde X, Y ∈ N (Não terminal)

e a ∈ T (Terminal)

A regra S → ε é permitido se S não aparece no lado direito de nenhuma regra.

Exemplo

X → ε 
X → a | aY
Y → b

Tipo - 2 gramática

Type-2 grammars gerar linguagens livres de contexto.

As produções devem estar no formato A → γ

Onde A ∈ N (Não terminal)

e γ ∈ (T ∪ N)* (String de terminais e não terminais).

Essas linguagens geradas por essas gramáticas são reconhecidas por um autômato pushdown não determinístico.

Exemplo

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

Tipo - 1 gramática

Type-1 grammarsgerar linguagens sensíveis ao contexto. As produções devem estar no formato

α A β → α γ β

Onde A ∈ N (Não terminal)

e α, β, γ ∈ (T ∪ N)* (Strings de terminais e não terminais)

As cordas α e β pode estar vazio, mas γ não deve estar vazio.

A regra S → εé permitido se S não aparecer no lado direito de nenhuma regra. As linguagens geradas por essas gramáticas são reconhecidas por um autômato linear limitado.

Exemplo

AB → AbBc 
A → bcA 
B → b

Tipo - 0 de gramática

Type-0 grammarsgerar linguagens recursivamente enumeráveis. As produções não têm restrições. Eles são qualquer gramática de estrutura de fase, incluindo todas as gramáticas formais.

Eles geram as linguagens que são reconhecidas por uma máquina de Turing.

As produções podem ser na forma de α → β Onde α é uma sequência de terminais e não terminais com pelo menos um não terminal e α não pode ser nulo. β é uma string de terminais e não terminais.

Exemplo

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