CI059-BCC1 - Introdução a Teoria da Computação
Primeiro Semestre de 2025
Profa. Carmem Hara

Autômatos, Computabilidade e Complexidade Computacional
Murilo Silva, 2017
Languages and Machines: An Introduction to the Theory of Computer Science
Thomas Sudkamp
Addison-Wesley, Second Edition, 1998
Elementos de Teoria da Computacao
Harry F. Lewis, C. H. Papadimitriou
2a Edicao, Editora Bookman
Introduction to Automata Theory, Languages and Computation
John E. Hopcroft, Jeffrey D. Ullman
Addison-Wesley, 1979
Theory of Computation
Wood, D., Ed. John Wiley & Sons, 1987
Introducao aos Fundamentos da Computacao
Newton Jose Vieira
Ed. Pioneira Thomson Learning, 2006

Aula 1: organizacao, as areas da teoria da computacao, linguagens [Slides]
Aula 2: conjuntos regulares e expressões regulares [Slides]
Aula 4: automatos finitos deterministicos
Aula 5: automatos finitos nao deterministicos
Aula 6: equivalencia automatos finitos - expressoes regulares
Aula 7: propriedades das linguagens regulares
Aula 8: gramaticas livres de contexto
Aula 9 : automato com pilha
Aula 10 : automato com pilha (continuacao)
Aula 11: analise sintatica
Aula 12: formas normais
Aula 13 : propriedades de linguagens livres de contexto - lema de bombeamento
Aula 14 : maquinas de Turing [Exemplo de MT de 2 trilhas]
Aula 15 : maquinas de Turing (continuacao) [Exemplo de MT para geração de sequências]
Aula 16 : Indecidibilidade

Lista 1: Linguagens, expressoes regulares e automatos finitos [.pdf]
Lista 2: Transformacoes de automatos, Lema de Bombeamento, Gramaticas Livres de Contexto [.pdf]
Lista 3: Apresente um autômato com pilha para as linguagens do Exercício 4 da Lista 2.
Lista 4: Linguagens livres de contexto [.pdf]
Lista 5: Máquinas de Turing [.pdf]