Linguagens Formais e Autômatos
Período letivo 2026.1:
- Campus Juazeiro
- Segundas, das 14:00 às 16:00 hs, laboratório de programação avançada
- Quartas, das 14:00 às 16:00 hs, laboratório de programação avançada
- Informações gerais
- Programa da disciplina
Material didático:
- Linguagens Formais: Teoria e Conceitos
Em co-autoria com os Profs. João José Neto e Ítalo Santiago Vega
Editora Blucher, 2023, ISBN 9786555067163, 608 páginas
- Linguagens Formais - Exercícios e Soluções
Marcus Vinicius Midena Ramos
Novatec Editora, 2021, ISBN 978-65-86057-59-1, 336 páginas
- Linguagens Formais: Teoria, Modelagem e Implementação
Em co-autoria com os Profs. João José Neto e Italo Santiago Vega
Editora Bookman 2009. ISBN 9788577804535. 656 páginas (fora de catálogo)
- Aulas gravadas
- 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
- 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 - 11/03/2026 - Apresentação e motivação.
Aula 02 - 16/03/2026 - Conjuntos.
Aula 03 - 18/03/2026 - Relações e funções.
Aula 04 - 23/03/2026 - Cardinalidade de conjuntos.
Aula 05 - 25/03/2026 - Símbolos, alfabetos, cadeias, sentenças e linguagens.
Aula 06 - 30/03/2026 - Gramáticas. Exemplos.
Aula 07 - 01/04/2026 - Exercícios de síntese de gramáticas.
Aula 08 - 06/04/2026 - Gramáticas equivalentes. Linguagens como conjuntos. Reconhecedores e autômatos. GLDs e GLEs.
Aula 09 - 08/04/2026 - Equivalências unitárias/não-unitárias, GLD/GLE e reversos.
Aula 10 - 13/04/2026 - Conjuntos regulares.
Aula 11 - 15/04/2026 - Expressões regulares e autômatos finitos.
Aula 12 - 22/04/2026 - Exemplos e exercícios de autômatos finitos determinísticos.
Aula 13 - 27/04/2026 - Autômatos finitos não determinísticos.
Aula 14 - 29/04/2026 - Transições em vazio. ERs <=> GRs.
Aula 15 - 04/05/2026 - GRs <=> AFs.
Aula 16 - 06/05/2026 - Prova 1.
Aula 17 - 13/05/2026 - ERs <=> AFs. Minimização de AFs.
Aula 18 - 18/05/2026 - Minimização.
Aula 19 - 20/05/2026 - Transdutores finitos. Pumping Lemma para as linguagens regulares (prova).
Aula 20 - 25/05/2026 - Pumping Lemma (aplicações).
Aula 21 - 27/05/2026 - Propriedades de fechamento. Questões decidíveis.
Aula 22 - 01/06/2026 - Linguagens e gramáticas livres de contexto.
Aula 23 - 03/06/2026 - Árvores de derivação. Ambiguidade.
Aula 24 - 08/06/2026 - Simplificação de gramáticas livres de contexto.
Aula 25 - 10/06/2026 - Formas Normais para gramáticas livres de contexto.
Aula 26 - 15/06/2026 - Autômatos de Pilha. Critérios de aceitação.
Aula 27 - 17/06/2026 - Pumping Lemma para as linguagens livres de contexto (prova e aplicações).
Aula 28 - 01/07/2026 - LLCs determinísticas. Propriedades de fechamento e questões decidíveis das LLCs.
Aula 29 - 06/07/2026 - Dúvidas para a prova.
Aula 30 - 08/07/2026 - Prova 2.
Segunda chamada - 10/07/2026.
Prova final - 13/07/2026.