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 → bTipo - 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 → bTipo - 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