Teoria da Computação / Linguagens Formais e Teoria da Computação
Ementa:
Linguagens Regulares e Autômatos Finitos Deterministicos; Expressões Regulares; Relação entre AFD's e Expressões Regulares; Autômatos Finitos Não-Deterministicos; Operações com Autômatos Finitos e Linguagens Regulares; Lema do Bombeamento para Linguagens Regulares; Gramáticas Regulares; Linguagens Livres de Contexto e Gramáticas Livres de Contexto; Árvores de Análise Sintática; Lema do Bombeamento para Linguagens Livres de Contexto; Autômatos de Pilha; Relação entre Gramáticas Livres de Contexto e Autômatos de Pilha; Máquina de Turing; Introdução à Teoria da Complexidade.
Bibliografia:
SIPSER, M. Introdução à Teoria da Computação, 2ª edição. Cengage Learning, ISBN, p. 978-85, 2007.
COUTINHO, S. C.; SCHECHTER, Luis Menasché. Autômatos, Linguagens Formais e Computabilidade. 2019.
Playlist:
Slides:
- Aula 0 - Apresentação do curso
- Aula 1 - Introdução a Teoria da Computação e AFDs
- Aula 2 - Construindo Autômatos
- Aula 3 - Operações Regulares e AFNs
- Aula 4 - AFNs, Equivalência com AFDs e Fechamento de Operações
- Aula 5 - Expressões Regulares e Algoritmo de Brzozowski
- Aula 6 - Gramáticas Regulares e Equivalências
- Aula 7 - Lema do Bombeamento
- Aula 8 - Linguagens Livres do Contexto
- Aula 9 - Forma Normal de Chomsky e Fechamento de LLC's
- Aula 10 - Autômato com pilha
- Aula 11 - Equivalência entre AP e GLC
- Aula 12 - Lema do Bombeamento para LLC
- Aula 13 - Máquinas de Turing
- Aula 14 - Composição de MTs
- Aula 15 - Generalizações de MTs e Fechamento
- Aula 16 - Problemas decidíveis
- Aula 17 - MT Universal e Linguagens Não-enumeráveis
- Aula 18 - A Indecidibilidade do Problema da Parada
- Aula 19 - Teoria da Complexidade
Atividades:
Se você tem alguma dúvida ou sugestão, sinta-se à vontade em me mandar uma mensagem. email.