Ementa: Estudo das linguagens formais da Hierarquia de Chomsky. Estudo dos formalismos matemáticos geradores, e/ou denotacionais, e reconhecedores de cada uma destas linguagens. Desenvolvimento da noção de computabilidade e decibilidade, e os problemas envolvidos, para o desenvolvimento de métodos de redução de problemas. Apresentação da Tese de Church e do Teorema da Incompletude de Gödel. Desenvolvimento dos conceitos sobre as classes de problemas P, NP, NP-Completo e NP-Difícil.

Bibliografia:
Bibliografia básica:
HOPCROFT, J. et al.. Introdução à Teoria de Autômatos, Linguagens e Computação. Editora: Campus. 2002.
LEWIS, H. R., PAPADIMITRIOU, C. H.. Elementos da Teoria da Computação. Editora: Bookman. 2a edição. 2004.
MENEZES, P. F. B.. Linguagens Formais e Autômatos. UFRGS. 3a edição. Editora: Sagra Luzzatto. 2002.
DIVERIO, T. A. e MENEZES, P. F. B.. Teoria da Computação: Máquinas Universais e Computabilidade. UFRGS. Editora: Sagra Luzzatto. 1999.
JONES, N. D.. Computability and Complexity from a Programming Perspective. Editora: The MIT Press. 1997.

Bibliografia complementar:
EPSTEIN, R., CARNIELLI, W.. Computability: Computable Functions, Logic, and the Foundations of Mathematics. 2nd edition. Editora: Wadsworth, 2000.


Pré-requisitos: Lógica aplicada a computação e Matemática discreta.