Linguagens Formais e Autômatos
Período letivo 2018.1:
Calendário de final de período:
- Aula extra 01: 06/09, 5ª feira
- Aula extra 02: 11/09, 3ª feira
- Aula extra 03: 13/09, 5ª feira
- Prova substitutiva: 18/08/2018, 3ª feira
- Prova final: 20/08/2018, 5ª 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 - 17/05 - Apresentação e motivação.
Aula 02 - 22/05 - Conjuntos.
Aula 03 - 24/05 - Relações, funções e cardinalidade de conjuntos.
Aula 04 - 05/06 - Cardinalidade de conjuntos.
Aula 05 - 07/06 - Símbolos, alfabetos, cadeias, linguagens e sentenças. Operações sobre linguagens.
Aula 06 - 12/06 - Operações sobre linguagens. Gramáticas, reconhecedores e enumerações. Equivalências. Gramáticas, formas sentenciais e derivações. Exemplo.
Aula 07 - 14/06 - Gramáticas e exemplo. Exercícios.
Aula 08 - 19/06 - Exercícios.
Aula 09 - 21/06 - Exercícios. Gramáticas equivalentes. Linguagens como conjuntos. Reconhecedores.
Aula 10 - 26/06 - Prova 1.
Aula 11 - 28/06 - Gramáticas e linguagens regulares regulares. Exemplos e exercícios.
Aula 12 - 03/07 - Exercícios. Equivalência GLDs e GLEs.
Aula 13 - 05/07 - Conjuntos e expressões regulares. Gramáticas unitárias e não-unitárias.
Aula 14 - 10/07 - Autômatos finitos. Exemplos.
Aula 15 - 12/07 - Exemplo e exercícios.
Aula 16 - 17/07 - Autômatos finitos não-determinísticos.
Aula 17 - 19/07 - Autômatos finitos com transições em vazio.
Aula 18 - 24/07 - Estados inúteis e inacessíveis. Ordem de aplicação dos algoritmos. Exemplos e exercícios.
Aula 19 - 26/07 - ER <-> GLD. AF <- GLD.
Aula 20 - 31/07 - AF -> GLD. ER <-> AF.
Aula 21 - 02/08 - Prova 2.
Aula 22 - 07/08 - Minimização.
Aula 23 - 09/08 - Exemplo. Transdutores finitos.
Aula 24 - 14/08 - Exercício. Pumping Lemma para as Linguagens Regulares.
Aula 25 - 16/08 - Exemplos e exercícios.
Aula 26 - 21/08 - Propriedades de fechamento para as linguagens regulares.
Aula 27 - 23/08 - Aplicações das propriedades de fechamento. Questões decidíveis para as linguagens regulares.
Aula 28 - 28/08 - Greve de alunos.
Aula 29 - 30/08 - Linguagens e gramáticas livres de contexto. Derivações mais à esquerda e mais à direita.
Aula 30 - 04/09 - Prova 03.
Aula 31 - 06/09 - Aula extra 01 - EBNF. Ávores de derivação. Ambiguidade.
Aula 32 - 11/09 - Aula extra 02 - Simplificação de GLCs. Formas Normais. Autômatos de Pilha. APs e GLCs.
Aula 33 - 13/09 - Aula extra 03 - LRs e LLCs. PL para LLCs. LLCs determinísticas. Propriedades de fechamento. Questões decidíveis e indecidíveis.