Prof. Marcus Ramos - Linguagens Formais e Autômatos

Linguagens Formais e Autômatos

Período letivo 2021.1 (2020.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)
A partir do dia 11/05 o novo endereço da nossa sala de aula virtual será https://meet.google.com/fqn-uzcr-znz
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 final (resolução)

Aulas ministradas:

Aula 01 - 02/03/2021 - Apresentação da disciplina (aula ao vivo)
Aula 02 - 04/03/2021 - Conjuntos e relações (aula ao vivo)
Aula 03 - 09/03/2021 - Funções e cardinalidade de conjuntos (aula gravada e plantão de dúvidas)
Aula 04 - 11/03/2021 - Cardinalidade de conjuntos. Símbolos, alfabeto, cadeias e sentenças (aula gravada e plantão de dúvidas)
Aula 05 - 16/03/2021 - Linguagens (aula gravada e plantão de dúvidas)
Aula 06 - 18/03/2021 - Gramáticas (aula gravada e plantão de dúvidas)
Aula 07 - 23/03/2021 - Exercícios de gramáticas (aula ao vivo)
Aula 08 - 25/03/2021 - Linguagens como conjuntos. Reconhecedores. Gramáticas regulares (aula gravada e plantão de dúvidas)
Aula 09 - 30/03/2021 - Gramáticas lineares à esquerda e à direita. Equivalências e linguagem reversa. Exercícios (aula ao vivo)
Aula 10 - 06/04/2021 - Conjuntos regulares. Exercícios (aula ao vivo)
Aula 11 - 08/04/2021 - Expressões regulares. Exercícios (aula ao vivo)
Aula 12 - 13/04/2021 - Autômatos finitos (aula ao vivo)
Aula 13 - 15/04/2021 - Autômatos finitos não-determinísticos (aula ao vivo)
Aula 14 - 20/04/2021 - Prova 1 (AVA, de 16/04 00:00h até 21/04 23:59h)
Aula 15 - 22/04/2021 - Eliminação de não-determinismos. Transições em vazio (aula ao vivo)
Aula 16 - 27/04/2021 - Eliminação de transições em vazio. Estados inacessíveis e inúteis (definição e eliminação) (aula ao vivo)
Aula 17 - 29/04/2021 - Equivalência entre conjuntos regulares e gramáticas lineares à direita (aula ao vivo)
Aula 18 - 04/05/2021 - Equivalência entre gramáticas lineares à direita e autômatos finitos. Conjunto regular => autômato finito (aula ao vivo)
Aula 19 - 06/05/2021 - Autômato finito => conjunto regular. Minimização, exceto algoritmo (aula ao vivo)
Aula 20 - 11/05/2021 - Algoritmo de minimização. Transdutores finitos (aula ao vivo)
Aula 21 - 13/05/2021 - "Pumping Lemma" para as linguagens regulares (aula ao vivo)
Aula 22 - 18/05/2021 - Aplicações do "Pumping Lemma". Propriedades de fechamento das linguagens regulares (aula ao vivo)
Aula 23 - 20/05/2021 - Questões decidíveis para as linguagens regulares. Linguagens e gramáticas livres de contexto (aula ao vivo)
Aula 24 - 25/05/2021 - Árvores de derivação. Ambigüidade (aula ao vivo)
Aula 25 - 27/05/2021 - Simplificação de gramáticas livres de contexto (aula ao vivo)
Aula 26 - 01/06/2021 - Formas normais para gramáticas livres de contexto (aula ao vivo). Autômatos de pilha (aula ao vivo)
Aula 27 - 08/06/2021 - Autômatos de pilha (aula ao vivo)
Aula 28 - 10/06/2021 - Prova 2 (AVA, de 10/06 00:00h até 13/06 23:59h)
Aula 29 -
Aula 30 -