Prof. Marcus Ramos - Linguagens Formais e Autômatos

Linguagens Formais e Autômatos

Período letivo 2022.2 (2022.1 no SIGA):

Campus Juazeiro
Terças, das 14:00 às 16:00 hs, sala 21
Quintas, das 14:00 às 16:00 hs, sala 15
As aulas de reposição em 2022 (três no total) acontecerão nos dias 17/11, 01/12 e 15/12, quintas-feiras, das 8:00h às 10:00h, no Laboratório de Programação Avançada
As aulas de reposição em 2023 (quatro no total) acontecerão em dias, horário e local a serem informados
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:

Aulas ministradas:

Aula 01 - 18/10/2022 - Apresentação e motivação.
Aula 02 - 20/10/2022 - Conjuntos.
Aula 03 - 25/10/2022 - Funções, relações.
Aula 04 - 27/10/2022 - Cardinalidade de conjuntos.
Aula 05 - 01/11/2022 - Símbolo, alfabeto, cadeia, sentença e linguagem formal. Fechamentos. Complementação. Reverso. Métodos finitos para representação de linguagens.
Aula 06 - 03/11/2022 - Gramáticas, derivações e linguagem definida por ma gramática.
Aula 07 - 08/11/2022 - Linguagem a^nb^nc^n. Exercícios de síntese gramatical.
Aula 08 - 10/11/2022 - Gramáticas equivalentes. Linguagens como conjuntos. Reconhecedores.
Aula 09 - 17/11/2022 - (reposição) - Gramáticas regulares (lineares à dreita e à esquerda). Exemplos.
Aula 10 - 17/11/2022 - Exercícios de síntese gramatical.
Aula 11 - 29/11/2022 - Prova 1.
Aula 12 - 01/12/2022 - (reposição) - Conjuntos regulares. Exemplos. Exercícios.
Aula 13 - 01/12/2022 - Expressões regulares. Exemplos. Exercícios.
Aula 14 - 06/12/2022 - Autômatos finitos.
Aula 15 - 08/12/2022 - Não-determinismo.
Aula 16 - 13/12/2022 - Transições em vazio, estados inúteis e inacessíves.
Aula 17 - 15/12/2022 - (reposição) - Equivalência GR/CR.
Aula 18 - 15/12/2022 - Equivalência GR/AF.
Aula 19 - 20/12/2022 - Equvalência CR/AF.
Aula 20 - 22/12/2022 - Minimização.

AFASTAMENTO PARA TRATAMENTO DE SAÙDE

Aula 21 - 17/01/2023 - Prova 2.

Atividade 1:
Aula 22 - 24/01/2023 - Transdutores Finitos.
Aula 23 - 26/01/2023 - Pumping Lemma para as Linguagens Regulares.

Atividade 2:
Aula 24 - 31/01/2023 - Propriedades de Fechamento.
Aula 25 - 02/02/2023 - Questões Decidíveis.

Atividade 3:
Aula 26 - 07/02/2023 - Gramáticas Livres de Contexto, Metalinguagens, BNF, BNF Estendida, Árvores de Derivação.
Aula 27 - 09/02/2023 - Ambigüidade

Atividade 4:
Aula 28 - 14/02/2023 - Simplificação de gramáticas livres de contexto.
Aula 29 - 16/02/2023 - Formas normais para gramáticas liivres de contexto e Autômatos de Pilha.