Prof. Marcus Ramos - Linguagens Formais e Autômatos

Linguagens Formais e Autômatos

Período letivo 2025.2:

Campus Juazeiro
Terças, das 14:00 às 16:00 hs, sala 19
Quintas, das 14:00 às 16:00 hs, sala 19
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 - 12/08/2025 - Apresentação e motivação.
Aula 02 - 14/08/2025 - Teoria de conjuntos.
Aula 03 - 19/08/2025 - Funções e relações.
Aula 04 - 21/08/2025 - Cardinalidade de conjuntos.
Aula 05 - 09/09/2025 - Símbolo, alfabeto, cadeia, sentença e linguagem.
Aula 06 - 11/09/2025 - Gramáticas. Exemplos e exercícios.
Aula 07 - 16/09/2025 - Exemplos e exercícios.
Aula 08 - 18/09/2025 - Linguagens como conjuntos. Reconhecedores e autômatos. Gramáticas e linguagens regulares.
Aula 09 - 23/05/2025 - GLE <=> GLD. Não unitárias <=> Unitárias. Exercícios.
Aula 10 - 25/05/2025 - Conjuntos regulares. Exercícios.
Aula 11 - 30/09/2025 - Expressões regulares. Exercícios.
Aula 12 - 02/10/2025 - Autômatos finitos. Exercícios.
Aula 13 - 09/10/2025 - Autômatos finitos não-determinísticos.
Aula 14 - 14/10/2025 - Autômatos finitos com transições em vazio.
Aula 15 - 16/10/2025 - Prova P1.
Aula 16 - 21/10/2025 - Eliminação de estados inúteis e inacessíveis. Ordem de aplicação dos algoritmos.
Aula 17 - 23/10/2025 - JFLAP.
Aula 18 - 11/11/2025 - ER <=> GLD. GLD <=> AF.
Aula 19 - 13/11/2025 - ER <=> AF. Minimização de AFs.
Aula 20 - 18/11/2025 - Minimização.
Aula 21 - 20/11/2025 - Transdutores finitos.
Aula 22 - 25/11/2025 - Suspensão de aulas pela Proen (alojamento Scientex).
Aula 23 - 27/11/2025 - Scientex.
Aula 24 - 29/11/2025 - "Pumping Lemma" para as linguagens regulares.
Aula 25 - 02/12/2025 - Propriedads de fechamento. Questões decidíveis.
Aula 26 - 04/12/2025 - Linguagens e gramáticas livres de contexto.
Aula 27 - 06/12/2025 - Simplificação gramatical. Formais normais.
Aula 28 - 09/12/2025 - Autômatos de pilha.
Aula 29 - 11/12/2025 - "Pumping Lemma" para as linguagens livres de contexto.
Aula 30 - 13/12/2025 - Prova P2.

Prova substitutiva - 16/12/2025.
Prova final - 18/12/2025.