Linguagens Formais e Autômatos
Período letivo 2017.2:
- Campus Juazeiro, sala 11
- Segundas, das 14:00 às 16:00 hs
- Quartas, das 14:00 às 16:00 hs
- Programa da disciplina
Datas importantes:
- Últimas aulas de 2017: dias 18 (7ª) e 20/12 (8ª)
- Primeira aula de 2018: dia 17/01 (9ª)
- Não haverá aula no dia 15/01
- Prova 1: dia 22/01 (10ª aula)
- Prova 2: dia 07/03 (20ª aula)
- 27ª aula: dia 02/04
- 28ª aula: dia 04/04
- 29ª aula: dia 09/04
- 30ª aula: dia 11/04
- 31ª aula: dia 13/04 (sala 14, das 10:00h às 12:00h)
- 32ª aula: dia 16/04 (prova 3)
- Prova final: dia 18/04
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/11 - Apresentação e motivação.
Aula 02 - 22/11 - Conjuntos.
Aula 03 - 27/11 - Relações, funções e cardinalidade de conjuntos.
Aula 04 - 29/11 - Cardinalidade de conjuntos. Símbolos, alfabetos, cadeias, sentenças e linguagens.
Aula 05 - 11/12 - Conceitos básicos de linguagens. Gramáticas, reconhecedores e enumerações.
Aula 06 - 13/12 - Gramáticas, exemplos e exercícios.
Aula 07 - 18/12 - Exercícios. Linguagens como conjuntos.
Aula 08 - 20/12 - Reconhecedores. Gramáticas lineares à esquerda e à direita. Exercícios.
Aula 09 - 17/01 - Gramáticas unitárias e não-unitárias. Conjuntos regulares. Expressões regulares. Exemplos e exercícios.
Aula 10 - 22/01 - Prova 1.
Aula 11 - 24/01 - Expressões regulares. Autômatos finitos.
Aula 12 - 31/01 - Exemplos e exercícios de autômatos finitos. Não-determinismo.
Aula 13 - 05/02 - Não-determinismo, exemplos e exercícios.
Aula 14 - 07/02 - Transiçoes em vazio. Estados inúteis e inacessíveis.
Aula 15 - 19/02 - Equivalência entre ERs e GLDs.
Aula 16 - 21/02 - Equivalência entre GLDs e AFs, e entre AFs e ERs.
Aula 17 - 26/02 - Minimização de autômatos finitos.
Aula 18 - 28/02 - Exercício de minimização. Transdutores finitos.
Aula 19 - 05/03 - Revisão e dúvidas para a prova.
Aula 20 - 07/03 - Prova 2.
Aula 21 - 12/03 - Pumping Lemma para as linguagens regulares.
Aula 22 - 14/03 - Exemplos de aplicação do PL. Propriedades de fechamento das linguagens regulares.
Aula 23 - 19/03 - Exemplos de aplicação das propriedades de fechamento. Questões decidíveis. Linguagens e gramáticas livres de contexto.
Aula 24 - 21/03 - Não-terminais auto-recursivos centrais. Aninhamentos e balanceamentos. Derivações mais à esquerda e mais à direita. BNF e EBNF.
Aula 25 - 26/03 - Árvores de derivação. Ambigüidade.
Aula 26 - 28/03 - Simplificação de gramáticas livres de contexto.
Aula 27 - 02/04 - Autômatos de Pilha.
Aula 28 - 04/04 - Equivalência dos critérios de aceitação. Equivalência entre gramáticas livres de contexto e autômatos de pilha.
Aula 29 - 09/04 - Pumping Lemma para as linguagens livres de contexto.
Aula 30 - 11/04 - Pumping Lemma para as linguagens livres de contexto - exemplos.
Aula 31 - 13/04 - Linguagens livres de contexto determinísticas e não-determinísticas. Propriedades de fechamento. Questão decidíveis e não-decidíveis. Linguagens e gramáticas sensíveis ao contexto. Máquinas de Turing. Hierarquia de Chomsky.
Aula 32 - 16/04 - Prova 3.