Carga Horária Teórica: 60 Horas.
Carga Horária Prática: 0 Horas.

Número de Créditos: 4.

Ementa: Classificação e propriedades das gramáticas. Problemas decidíveis em cada classe de gramática e respectivas linguagens. Autômatos "linear-bounded" e máquinas de Turing como reconhecedores de linguagens. Noções de "parsing". "Parsing" determinístico. Gramáticas LL(k) e LR(k).

Bibliografia Básica:

- Aho, A.E.; Hopcroft, J.E. & Ullman, J.D.: The Design and Analysis of Computer Algorithms.Addison-Wesley Publishing Company, 1974.
- Hopcroft, J.E. & Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.