Linguagens Formais e Autômatos
Período letivo 2016.1:
Calendário de final de período:
- Aula de reposição: 29 de julho, 6ª feira, 14:00h
- Prova 3: 05 de agosto, 6ª feira, 14:00h
- Prova 4: 09 de agosto, 3ª feira, 16:00h
- Segunda chamada: 10 de agosto, 4ª feira, 14:00 h
- Prova final: 12 de agosto, 6ª feira, 14:00h
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 - 26/04 - Apresentação e motivação.
Aula 02 - 28/04 - Conjuntos, relações, funções e conjuntos enumeráveis.
Aula 03 - 03/05 - Símbolos, alfabetos, cadeias, sentenças, gramáticas e reconhecedores.
Aula 04 - 05/05 - Gramáticas, formas sentenciais e derivações.
Aula 05 - 10/05 - Exercícios sobre gramáticas.
Aula 06 - 12/05 - Exercícios sobre gramáticas. Linguagens como conjuntos. Reconhecedores. Gramáticas regulares.
Aula 07 - 17/05 - Exercícios sobre gramáticas regulares. Conjuntos regulares. Exercícios sobre conjuntos regulares. Expressões regulares. Exercícios sobre expressões regulares.
Aula 08 - 19/05 - Autômatos finitos. Exercícios sobre autômatos finitos.
Aula 09 - 24/05 - Autômatos finitos não-determinísticos. Exemplos.
Aula 10 - 31/05 - Prova 1.
Aula 11 - 02/06 - Autômatos finitos com transições em vazio. Estados inacessíveis e inúteis. Exercícios.
Aula 12 - 07/06 - Equivalência entre expressões regulares e gramáticas lineares à direita. Equivalência entre gramáticas lineares à direita e autômatos finitos.
Aula 13 - 09/06 - Equivalência entre expressões regulares e autômatos finitos. Minimização de autômatos finitos.
Aula 14 - 16/06 - Exercícios de minimização Transdutores finitos.
Aula 15 - 21/06 - Exercícios de transdutores finitos. Pumping Lemma para as linguagens regulares.
Aula 16 - 23/06 - Exemplos de aplicação do PL. Propriedadesde de fechamento.
Aula 17 - 28/06 - Questões decidíveis. Introdução às linguagens e gramáticas livres de contexto.
Aula 18 - 30/06 - BNF, BNF estendido, árvores de derivação e ambiguidade.
Aula 19 - 05/07 - Revisão e exercícios.
Aula 20 - 07/07 - Prova 2.
Aula 21 - 12/07 - Simplificação de gramáticas livres de contexto.
Aula 22 - 14/07 - Formas normais. Autômatos de pilha.
Aula 23 - 19/07 - Exemplos e exercícios. Equivalência dos critérios de aceitação. GLC -> AP.
Aula 24 - 21/07 - AP -> GLC. Pumping Lemma para as linguagens livres de contexto.
Aula 25 - 26/07 - Exemplos. Linguagens Livres de Contexto Não-Determinísticas e Determinísticas. Propriedades de fechamento.
Aula 26 - 28/07 - Propriedades de fechamento. Questões decidíveis e não-decidíveis. Linguagens e gramáticas sensíveis ao contexto.
Aula 27 - 29/07 - Máquinas de Turing com fita limitada. LSCs e GSCs x LLCs e GLCs.
Aula 28 - 02/08 - LREs e gramáticas irrestritas. Hierarquia de Chmsky e conclusões finais. Dúvidas e revisão.
Aula 29 - 04/08 - Dúvidas e revisão.
Aula 30 - 05/08 - Prova 3.
Aula 31 - 09/08 - Prova 4.