| Ementa/Descrição: |
Problemas e linguagens. Modelos computacionais uniformes clássicos e a hierarquia de Chomsky-Turing. Linguagens regulares: autômatos finitos determinísticos e não determinísticos, expressões regulares e o teorema de Kleene; lemas de iteração regulares. Linguagens livres de contexto: autômatos com pilha e gramáticas livres de contexto determinísticos e não determinísticos; formas gramaticais normais de Chomsky e Greibach; lema de iteração livre de contexto. Linguagens recursivamente enumeráveis e recursivas: máquinas de Turing determinísticas e não determinísticas; máquinas universais, diagonalização, indecidibilidade e linguagens não recursivamente enumeráveis; reduções de Turing e máquinas com oráculos; tese de Church-Turing. Decidibilidade em tempo polinomial: cômputo versus verificação e as classes de complexidade P, NP e coNP de linguagens; intratabilidade e o problema P = NP; reduções em tempo polinomial, elementos do teorema de Cook-Levin, linguagens NP-completas e NP-difíceis.
|
| Referências: |
HOPCROFT, John E.; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introduction to Automata Theory, Languages, and Computation. 3rd ed. [S.l.]: Addison-Wesley-Longman, 2006. (Addison-Wesley series in computer science).
LEWIS, Harry R.; PAPADIMITRIOU, Christos H. Elements of the Theory of Computation. 2nd ed. [S.l.]: Prentice Hall, 1998.
SIPSER, Michael. Introduction to the Theory of Computation. 3rd ed. [S.l.]: Cengage Learning, 2013.
BIBLIOGRAFIA COMPLEMENTAR
ANDERSON, James A. Automata Theory with Modern Applications. [S.l.]: Cambridge University Press, 2006. ISBN 978-0-521-61324-8. DOI: 10.1017/CBO9780511607202.
CRESPI-REGHIZZI, Stefano; BREVEGLIERI, Luca; MORZENTI, Angelo. Formal Languages and Compilation. 3rd ed. [S.l.]: Springer, 2019. (Texts in Computer Science). ISBN 978-3-030-04878-5. DOI: 10.1007/978-3-030-04879-2.
GOLDREICH, Oded. P, NP, and NP-Completeness: The Basics of Complexity Theory. [S.l.]: Cambridge University Press, 2010. ISBN 978-0-521-19248-4. DOI: 10.1017/CBO9780511761355.
KOZEN, Dexter. Automata and Computability. [S.l.]: Springer-Verlag, 1997. (Undergraduate Texts in Computer Science). ISBN 978-0-387-94907-9. DOI: 10.1007/978-1-4612-1844-9.
SHALLIT, Jeffrey O. A Second Course in Formal Languages and Automata Theory. [S.l.]: Cambridge University Press, 2008. ISBN 978-0-521-86572-2. DOI: 10.1017/CBO9780511808876.
|
