Prof. Marcus Ramos - Linguagens Formais e Autômatos

Linguagens Formais e Autômatos

Período letivo 2020.3:

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 Í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:

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

Aulas ministradas:

Aula 01 - 15/09/2020 - Apresentação da disciplina.
Aula 02 - 17/09/2020 - Conjuntos e relações.
Aula 03 - 22/09/2020 - Funções e cardinalidade de conjuntos.
Aula 04 - 24/09/2020 - Cardinalidade de conjuntos. Símbolos, alfabeto, cadeias e sentenças.
Aula 05 - 29/09/2020 - Linguagens.
Aula 06 - 01/10/2020 - Gramáticas.
Aula 07 - 06/10/2020 - Exercícios de síntese de gramáticas.
Aula 08 - 08/10/2020 - Linguagens como conjuntos. Reconhecedores. Gramáticas regulares.
Aula 09 - 13/10/2020 - Gramáticas lineares à direita e à esquerda.
Aula 10 - 15/10/2020 - Conjuntos regulares. Exercícios.
Aula 11 - 20/10/2020 - Expressões regulares.
Aula 12 - 22/10/2020 - Autômatos finitos.
Aula 13 - 27/10/2020 - Autômatos finitos não-determinísticos.
Aula 14 - 29/10/2020 - Eliminação de não-determinismos. Autômato finito com transições em vazio.
Aula 15 - 10/11/2020 - Revisão para a prova.
Aula 16 - 12/11/2020 - Prova 1.
Aula 17 - 24/11/2020 - Eliminação de transições em vazio. Estados inacessíveis e inúteis.
Aula 18 - 26/11/2020 - Equivalência entre gramáticas lineares à direita e conjuntos regulares.
Aula 19 - 01/12/2020 - Equivalência entre gramáticas lineares à direita e autômatos finitos. Equivalência entre conjuntos regulares e autômatos finitos.
Aula 20 - 03/12/2020 - Minimização de autômatos finitos.
Aula 21 - 08/12/2020 - Transdutores finitos.
Aula 22 - 10/12/2020 - Linguagens que não são regulares.
Aula 23 - 15/12/2020 - Prova 2.
Aula 24 -
Aula 25 -
Aula 26 -
Aula 27 -
Aula 28 -
Aula 29 -
Aula 30 -
Aulas 24 a 30 - Atividade (Prova 3) para ser entregue até o próximo dia 22/12.