Estudo de vários formalismos para computação e algoritmos e as limitações de certas formas de computação.
Palavras, linguagens, operações sobre linguagens. Linguagens regulares. Autômatos finitos determinísticos e não determinísticos. Teorema de Kleene. Autômatos reduzidos. Modelos de computação; máquinas de Turing. Tese de Church. Redutibilidade e problemas indecidíveis. Complexidade, problemas decidíveis em tempo polinomial. Não-determinismo versus determinismo. Redutibilidade e problemas NP-completos. Teorema de Cook-Levin.
A.V. Aho, R. Sethi, J.D. Ullman, Compilers, Principles, Techniques and Tools>/i>, Addison-Wesley, 1986.J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Weley, 2000.H.R. Lewis, C.H. Papadimitriou, Elementos de Teoria da Computação, 2nd ed., Bookman, 2000.P.B. Menezes, Linguagens Formais e Autômatos, 3a ed., Sagra Luzzatto, Porto Alegre, 2000.M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2012.
