Prof. Marcus Ramos - Linguagens Formais e Autômatos

Linguagens Formais e Autômatos

Período letivo 2021.3 (2021.1 no SIGA):

Campus Juazeiro
Terças, das 14:00 às 16:00 hs (sala virtual do Google Meet)
Quintas, das 14:00 às 16:00 hs (sala virtual do Google Meet)
Informações gerais
Programa da disciplina

Material didático:

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
Linguagens Formais - Exercícios e Soluções
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:

Prova 1 (resolução)
Prova 2 (resolução)
Prova final (resolução)

Aulas ministradas:

Aula 01 - 30/11/2021 - Apresentação e motivação.
Aula 02 - 02/12/2021 - Conjuntos.
Aula 03 - 07/12/2021 - Relações. Funções.
Aula 04 - 09/12/2021 - Cardinalidade de conjuntos.
Aula 05 - 14/12/2021 - Símbolo, alfabeto, cadeia, sentença e linguagem.
Aula 06 - 16/12/2021 - Gramáticas, reconhecedores e enumerações.
Aula 07 - 21/12/2021 - Gramáticas. Exemplos e exercícios.
Aula 08 - 11/01/2022 - Linguagens e Conjuntos.
Aula 09 - 13/01/2022 - Autômatos e Reconhecedores.
Aula 10 - 18/01/2022 - Linguagens e Gramáticas Regulares.
Aula 11 - 20/01/2022 - Conjuntos e Expressões Regulares.
Aula 12 - 25/01/2022 - Autômatos finitos.
Aula 13 - 27/01/2022 - Autômatos finitos. Exemplos e exercícios.
Aula 14 - 01/02/2022 - Revisão para Prova 1.
Aula 15 - 03/02/2022 - Prova 1.
Aula 16 - 08/02/2022 - Autômatos finitos não-determinísticos.
Aula 17 - 10/02/2022 - Autômatos finitos com transições em vazio.
Aula 18 - 15/02/2022 - Estados inacessíveis e inúteis. Ordem de aplicação dos algoritmos.
Aula 19 - 17/02/2022 - Gramáticas lineares à direita <-> expressões regulares.
Aula 20 - 03/03/2022 - Gramáticas lineares à direita <-> autômatos finitos. Expressões regulares -> autômatos finitos.
Aula 21 - 08/03/2022 - Autômatos finitos -> expressões regulares.
Aula 22 - 10/03/2022 - Minimização de autômatos finitos.
Aula 23 - 15/03/2022 - Transdutores finitos.
Aula 24 - 17/03/2022 - Pumping Lemma - enunciado e prova.
Aula 25 - 22/03/2022 - Pumping Lemma - aplicações.
Aula 26 - 24/03/2022 - Propriedades de fechamento.
Aula 27 - 29/03/2022 - Questões decidíveis.
Aula 28 - 31/03/2022 - Linguagens e gramáticas livres de contexto. Exercícios.