CI059-BCC2 - Introdução a Teoria da Computação
Segundo Semestre de 2023
Profa. Carmem Hara

Horário para ver a prova: 28/novembro, terça-feira, entre 13:30h e 14h, na sala de aula.

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 no Teams: Entre na sala
Aula 2: conjuntos regulares e expressões regulares [Slides]
- Aula no Teams: Entre na sala
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] [solucão]
Lista 2: Transformacoes de automatos, Lema de Bombeamento, Gramaticas Livres de Contexto [.pdf] [solucão]
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] [solucão]
Lista 5: Máquinas de Turing [.pdf] [solucão]