Linguagens regulares e autômatos finitos; autômatos finitos determinísticos e não determinísticos e sua equivalência; Lema do bombeamento para linguagens regulares; gramáticas livres de contexto; autômatos de pilha e equivalência com gramáticas livres de contexto; gramáticas que não são livres de contexto; máquinas de Turing: definição e exemplos; máquina de turing universal; máquina de turing não determinística; a tese de Church-Turing; recursividade ou decidibilidade; linguagens recursivas e problemas decidíveis; o problema da parada; teorema de Rice; problema da correspondência de Post; Complexidade Computacional; a classe de problemas P; a classe de problemas NP; reduções em tempo polinomial; teoria da NP-completude; teorema de Cook-Levin; problemas NP-completos, e exemplos de provas de NP-completude.

Referências:

  1. SIPSER, M. Introduction to the Theory of Computation. 3. ed. São Paulo: Cengage Learning, 2012.
  2. LEWIS, H. R.; PAPADIMITRIOU, C. H. Elements of the Theory of Computation. 2. ed. Englewood Cliffs, N.J.: Prentice Hall PTR, 1997.
  3. HOPCROFT, J. E.; MOTWANI, R.; ULLMAN, J. D. Introduction to Automata Theory, Languages, and Computation. 3. ed. Upper Saddle River, NJ: Addison-Wesley Longman Publishing Co., Inc., 2006.

Bibliografia complementar: 

  1. ARORA, S.; BARAK, B. Computational Complexity: A Modern Approach. Cambridge: Cambridge University Press, 2009.
  2. KOZEN, D. C. Theory of Computation (Texts in Computer Science). Berlin: Springer-Verlag, 2006.
  3. PAPADIMITRIOU, C. H. Computational Complexity. Upper Saddle River, NJ: Addison-Wesley, 1993.
  4. GAREY, M. R.; JOHNSON, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman, c1979.
  5. PAPADIMITRIOU, C. H.; STEIGLITZ, K. Combinatorial optimization: algorithms and complexity. Englewood Cliffs, N.J.: Prentice-Hall, c1982.