Linguagens Formais e Autômatos
Período letivo 2017.1:
Aulas de reposição:
- 29/07 (sala 24), 05/08 (sala 14), 26/08 (sala 14) e 02/09 (sala 14)
- Sábados, das 8:00 às 10:00 hs
- Campus Juazeiro
Calendário de final de período:
- 03/10 - Prova 3
- 17/10 - Prova final
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:
Aulas ministradas:
Aula 01 - 20/06 - Apresentação e motivação.
Aula 02 - 22/06 - Conjuntos, relações e funções.
Aula 03 - 27/06 - Cardinalidade de conjuntos.
Aula 04 - 29/06 - Símbolos, alfabetos, cadeias, sentenças e linguagens.
Aula 05 - 04/07 - Gramáticas, formas sentenciais e derivações. Linguagem definida por uma gramática. Exemplos.
Aula 06 - 06/07 - Exercícios de síntese de gramáticas.
Aula 07 - 25/07 - Reconhecedores. Gramáticas lineares à direita e à esquerda. Exercícios.
Aula 08 - 27/07 - Conjuntos e expressões regulares. Exercícios.
Aula 09 - 29/07 - Autômatos finitos. Exercícios.
Aula 10 - 01/08 - Prova 1.
Aula 11 - 03/08 - Autômatos finitos não-determinísticos e com transições em vazio.
Aula 12 - 05/08 - Estados inúteis e inacessíveis. CR -> GLD. GLD -> CR (início).
Aula 13 - 08/08 - GLD -> CR (continuação). GLD <-> AF. CR -> AF.
Aula 14 - 10/08 - AF -> CR. Minimização de AFs.
Aula 15 - 15/08 - Minimização de AFs. Transdutores Finitos. Pumping Lemma.
Aula 16 - 17/08 - Pumping Lemma, exemplos, aplicações e exercícios. Propriedades de fechamento (até intersecção).
Aula 17 - 22/08 - Propriedades de fechamento (conclusão). Questões decidíveis.
Aula 18 - 24/08 - Linguagens e gramáticas livres de contexto.
Aula 19 - 26/08 - Dúvidas e revisão.
Aula 20 - 29/08 - Prova 2.
Aula 21 - 31/08 - BNF e EBNF. Derivações mais à esquerda e mais à direita. Árvores de derivação. Ambiguidade.
Aula 22 - 02/09 - Simplificação de GLCs: símbolos inúteis, símbolos inacessíveis, regras vazias e regras unitárias.
Aula 23 - 05/09 - Forma Normal de Chomsky. Forma Normal de Greibach. Autômatos de pilha.
Aula 24 - 12/09 - Critérios de aceitação. GLCs e APs.
Aula 25 - 14/09 - LLCs e LRs. Pumping Lemma para as LLCs.
Aula 26 - 19/09 - Aplicação do PL. Propriedades de fechamento das LLCs. Questões decidíveis das LLCs. Linguagens e gramáticas sensíveis ao contexto.
Aula 27 - 21/09 - Formas normais para GSCs. Máquina de Turing com fita limitada. GSCs e MTFL. LSCs e LLCs.
Aula 28 - 26/09 - Linguagens que não são sensíveis ao contexto (LR). Hierarquia de Chomsky e conclusões finais.
Aula 29 - 28/09 - Dúvidas e revisão.
Aula 30 - 03/10 - Prova 3.