Linguagens Formais e Autômatos

Notas e faltas: disponíveis no SIGA.

Período letivo 2012.1:

• Campus Juazeiro, sala 21
• Terças, das 10:00 às 12:00 hs
• Quintas, das 10:00 às 12:00 hs
• Programa da disciplina
• PUD

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

Slides:

• Elementos de matemática discreta
• Conceitos básicos de linguagens
• Linguagens regulares
• Linguagens livres de contexto
• Linguagens sensíveis ao contexto
• Conclusões

Avaliações:

• Prova 1 (resolução)
• Prova 2 (resolução)
• Prova final (resolução)
• Trabalho

Aulas ministradas:

2012-03-06 Apresentação da disciplina.

2012-03-08 Conjuntos e relações.

2012-03-13 Funções e conjuntos enumeráveis.

2012-03-15 Símbolos, alfabetos, cadeias e linguagens. Operações básicas sobre linguagens. Métodos para representação de linguagens.

2012-03-20 Gramáticas. Exemplos e exercícios.

2012-03-22 Exercícios sobre gramáticas. Gramáticas equivalentes.

2012-03-27 Gramáticas lineares à direita e lineares à esquerda. Exercícios. Reconhecedores.

2012-03-29 Gramáticas unitárias e não-unitárias. Exercícios. Conjuntos regulares e expressões regulares. Exercícios.

2012-04-03 Autômatos finitos. Exercícios.

2012-04-10 Autômatos finitos não-determinísticos.

2012-04-12 Autômatos finitos com transições em vazio. Exercícios. Conjuntos regulares => gramáticas lineares à direita.

2012-04-17 GLD => CR. GLD <=> AF. CR => AF.

2012-04-19 AF => CR. Minimização de autômatos finitos.

2012-04-24 Transdutores finitos.

2012-05-03 Prova 1.

2012-05-08 Pumping Lemma para as linguagens regulares.

2012-05-10 Propriedades de fechamento. Questões decidíveis.

2012-05-15 Questões decidíveis. Linguagens e gramáticas livres de contexto.

2012-05-17 BNF estendida. Derivações canônicas. Ambiguidade. Árvores de derivação.

2012-05-22 Simplificação de gramáticas livres de contexto.

2012-05-24 Forma Normal de Chomsky. Autômatos de pilha.

2012-05-29 Equivalência entre gramáticas livres de contexto e autômatos de pilha.

2012-05-31 Pumping Lemma para as linguagens livres de contexto. Linguagens livres de contexto não-determinísticas.

2012-06-05 Propriedades de fechamento e questões decidíveis das linguagens livres de contexto.

2012-06-12 Linguagens e gramáticas sensiveis ao contexto.

2012-06-14 Máquina de Turing com fita limitada. Linguagens que não são sensíveis ao contexto.

2012-06-19 Linguagens recursivas e recursivamente enumeráveis. Conclusões e próximos passos.

2012-06-21 Revisão para a prova.

2012-06-26 Apresentação dos trabalhos.

2012-06-28 Prova 2.

2012-07-03 Segunda chamada.

2012-07-05 Prova final.