Hierarquia de Chomsky

---

A Hierarquia de Chomsky é uma classificação de gramáticas formais em 4 níveis de complexidade crescente (Tipo 3 a 0).

1. Linguagens Regulares
   • Expressões regulares
   • Autômato Finito Determinístico - AFD
   • Autômato Finito Não Determinístico - AFND
   • Autômato Finito Não Determinístico com Transições Vazias - eFND
2. Linguagens Livre de Contexto
   • Autômato com pilha
3. Linguagens Sensíveis ao Contexto
   • Máquina de Turing com fita limitada
4. Linguagens Recursivamente Enumeráveis
   • Máquina de Turing com fita ilimitada

Referências

---