Hierarquia de Chomsky

A hierarquia de Chomsky é a inclusão estrita Tipo 3 ⊂ Tipo 2 ⊂ Tipo 1 ⊂ Tipo 0 entre quatro classes de linguagens formais. Tipo 3 são as regulares; Tipo 0, as recursivamente enumeráveis. Cada tipo reúne as produções permitidas, as linguagens geradas e o reconhecedor — AF, APND, ALLN ou MT.

Produções não contráteis e irrestritas deste tópico — e linguagens RE e a parada no tópico seguinte — partem dessa inclusão e da memória de cada máquina.

As páginas se agrupam em três blocos. O primeiro monta o mapa: inclusão estrita, reconhecedor de cada tipo, fechamento sob ∩ e duas pilhas equivalentes a uma MT.

O segundo escreve o Tipo 1: |α|≤|β| ou αAβ → αγβ, e as produções que geram {aⁿbⁿcⁿ}.

O terceiro trata do Tipo 0: α→β pode encolher, gera exatamente as RE, e constrói uma direção GI → MT.

Colocar {aⁿbⁿcⁿ} no Tipo 1 e reconhecê-la num ALLN está em A Hierarquia de Chomsky. As produções S→aSBC | aBC, CB→BC e o teste |α|≤|β| estão em Gramáticas e Linguagens Sensíveis ao Contexto.

A cadeia que não encolhe, salvo S→ε isolado, está em Gramáticas e Linguagens Sensíveis ao Contexto. A produção com |β|<|α| está em Gramática Irrestrita.

L_halt no mapa do Tipo 0 e AP de duas pilhas ≡ MT estão em A Hierarquia de Chomsky. A forma α→β com um não-terminal em α, e a simulação GI → MT, estão em Gramática Irrestrita.

{aⁿbⁿ} via S→aSb | ε é o exemplo de Tipo 2 em A Hierarquia de Chomsky. O contraste entre esse S→aSb de contexto vazio e a forma αAβ → αγβ está em Gramáticas e Linguagens Sensíveis ao Contexto.