Autômatos e Linguagens Formais

Texto introdutório e bem diagramado que parte da pergunta sobre o que é computação e avança por autômatos finitos, autômatos com pilha, gramáticas livres de contexto, máquinas de Turing, decidibilidade e NP-completude. Os exercícios ao fim de cada seção ajudam você a fixar cada conceito antes de seguir.

Murilo Vicente Gonçalves da Silva

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

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