Autômatos, Computabilidade e Complexidade Computacional

Notas de aula objetivas que vão das expressões regulares e autômatos finitos às linguagens livres de contexto, máquinas de Turing, decidibilidade e complexidade, incluindo problemas NP-completos clássicos. Um material enxuto para quem quer a teoria completa sem rodeios.

Jerônimo C. Pellegrini

Notas de aula escritas com clareza que constroem passo a passo autômatos finitos, expressões regulares, lema do bombeamento, gramáticas livres de contexto, autômatos de pilha e máquinas de Turing. Os exemplos trabalhados e as listas de exercícios tornam o material ideal para estudar sozinho.

S. C. Coutinho

Apostila extensa e detalhada que percorre toda a hierarquia de Chomsky, das linguagens regulares e autômatos finitos às linguagens livres de contexto, sensíveis ao contexto e recursivamente enumeráveis, com máquinas de Turing e muitos exemplos resolvidos. Começa revisando a matemática discreta necessária, então funciona bem para quem chega à disciplina pela primeira vez.

Marcus Vinícius Midena Ramos

Um percurso completo pela teoria da computação, dos autômatos e linguagens às máquinas de Turing, à computabilidade e à complexidade computacional, com o teorema de Rice, o teorema de Savitch e o problema P versus NP. Cada capítulo traz uma lista extensa de exercícios para consolidar o que você estudou.

Carlos Caleiro, F. Miguel Dionísio, Paula Gouveia, Jaime Ramos, João Rasga