Linguagens Formais e Autômatos
Período letivo 2019.1:
Calendário de final de período:
- Prova final: 27/08/2019, 3ª feira
Material didático:
- Linguagens Formais: Teoria, Modelagem e Implementação
Em co-autoria com os Profs. João José Neto e Ítalo Santiago Vega
Editora Bookman 2009. ISBN 9788577804535. 656 páginas
- JFLAP - um simulador gráfico e interativo para experimentação com gramáticas, expressões regulares e autômatos:
- Download (renomeie para "JFLAP.jar" caso o seu S.O. modifique o nome para "JFLAP.zip")
- Site
- Livro "Foundations of Computer Science" de A.V. Aho e J.D. Ullman, disponível para download gratuito na página dos autores:
- Capítulo 7 - The Set Data Model
- Capítulo 10 - Patterns, Automata, and Regular Expressions
- Capítulo 11 - Recursive Description of Patterns
- 40 exercícios sobre linguagens regulares, com solução.
- Documentário Dangerous Knowledge, de David Malone para a BBC, sobre as vidas e obras de Cantor, Boltzmann, Gödel e Turing.
Slides:
Avaliações:
Aulas ministradas:
Aula 01 - 23/04 - Apresentação e motivação.
Aula 02 - 25/04 - Conjuntos.
Aula 03 - 30/04 - Relações e funções.
Aula 04 - 02/05 - Conjuntos enumeráveis. Conceitos básicos de linguagens.
Aula 05 - 07/05 - Símbolos, alfabetos, cadeias, sentenças e linguagens. Meta-linguagens.
Aula 06 - 09/05 - Gramáticas. Exercícios.
Aula 07 - 14/05 - Exercícios. Linguagens como conjuntos. Reconhecedores.
Aula 08 - 16/05 - Gramáticas regulares. Exercícios.
Aula 09 - 21/05 - Conjuntos e expressões regulares.
Aula 10 - 23/05 - Prova 1.
Aula 11 - 28/05 - Autômatos finitos. Exemplos. Exercícios.
Aula 12 - 30/05 - Autômatos finitos não-determinísticos.
Aula 13 - 04/06 - Autômatos finitos com transições em vazio.
Aula 14 - 11/06 - Estados inacessíveis e inúteis. Ordem de aplicação dos algoritmos. Equivalência entre conjuntos (expressões) regulares e gramáticas lineares à direita.
Aula 15 - 13/06 - Devolução da prova1.
Aula 16 - 18/06 - Equivalência entre gramáticas lineares à direita e autômatos finitos. Expressões regulares -> autômatos finitos.
Aula 17 - 25/06 - Autômatos finitos -> Expressões regulares. Minimização de autômatos finitos.
Aula 18 - 27/06 - Minimização de autômatos finitos. Exemplos e exercícios.
Aula 19 - 04/07 - Transdutores finitos. Exemplos e exercícios.
Aula 20 - 09/07 - Prova 2.
Aula 21 - 11/07 - Pumping Lemma para as linguagens regulares.
Aula 22 - 23/07 - Pumping Lemma para as linguagens regulares. Exemplos e exercícios. Propriedades de fechamento das linguagens regulares.
Aula 23 - 30/07 - Questões decidíveis para as linguagens regulares. Linguagens e gramáticas livres de contexto.
Aula 24 - 01/08 - Linguagens e gramáticas livres de contexto. Metalinguagens. EBNF.
Aula 25 - 06/08 - Árvores de derivação. Derivações canônicas. Ambigüidade.
Aula 26 - 08/08 - Simplificação de gramáticas livres de contexto.
Aula 27 - 13/08 - Ordem de aplicação dos algoritmos de simplificação gramatical. Formas Normais. Autômato de Pilha.
Aula 28 - 15/08 - Autômato de Pilha. Exemplos e exercícios. GLCs x APs.
Aula 29 - 20/08 - LRs x LLCs. Pumping Lemma para as LLCs. Exemplos e aplicações.
Aula 30 - 22/08 - Prova 3.
Aula 31 - 29/08 - (extra) Propriedades de fechamento das LLCs. Questões decídíveis das LLCs. Linguagens e gramáticas sensíveis ao contexto. Máquina de Turing. Hierarquia de Chomsky.