Linguagens Formais e Autômatos

Período letivo 2010.1:

• Campus Juazeiro, sala 12
• Terças e quintas, das 14:00 às 16:00hs
• Programa da disciplina
• PUD

Atenção para o calendário de final de semestre:

• 15/06, terça-feira, não haverá aula;
• 17/06, quinta-feira, aula normal (das 13:00 às 16:00hs);
• 22/06, terça-feira, aula normal (das 14:00 às 16:00hs);
• 29/06, terça-feira, aula normal (das 14:00 às 16:00hs);
• 01/07, quinta-feira, prova 2 (das 14:00 às 16:00hs);
• 06/07, terça-feira, prova final (das 14:00 às 16:00hs).

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 Sicence" de A.V. Aho e J.D. Ullman, disponível para download gratuito na página dos autores (capítulo 10).

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)
• Projetos
• Grupos
• Notas - NOVO! (com prova final)

Aula 01 - 04/04 - Apresentação e motivação.

Aula 02 - 09/03 - Conjuntos e relações.

Aula 03 - 11/03 - Funções e conjuntos enumeráveis.

Aula 04 - 16/03 - Símbolos, alfabetos, cadeias e linguagens.

Aula 05 - 18/03 - Gramáticas.

Aula 06 - 23/03 - Linguagens como conjuntos. Reconhecedores.

Aula 07 - 25/03 - Gramáticas lineares. Conjuntos e expressões regulares.

Aula 08 - 30/03 - Expressões regulares. Autômatos finitos determinísticos.

Aula 09 - 06/04 - Autômatos finitos não-determinísticos.

Aula 10 - 08/04 - Autômatos finitos com transições em vazio. Estados inacessíveis e inúteis. JFLAP.

Aula 11 - 13/04 - Expressões regulares <> gramáticas lineares à direita. Gramáticas lineares à direita > autômatos finitos.

Aula 12 - 20/04 - Autômatos finitos > gramáticas lineares à direita. Expressões regulares <> autômatos finitos.

Aula 13 - 22/04 - Minimização de autômatos finitos. Exercícios.

Aula 14 - 27/04 - (3hs) - Prova 1.

Aula 15 - 29/04 - Discussão sobre a prova. Transdutores finitos.

Aula 16 - 04/05 - Pumping lemma para as linguagens regulares.

Aula 17 - 06/05 - (3hs) - Exercícios. Propriedades de fechamento das linguagens regulares.

Aula 18 - 11/05 - Questões decidíveis das linguagens regulares . Linguagens e gramátias livres de contexto.

Aula 19 - 13/05 - Auto-embutimento. Árvores de derivação. BNF/EBNF.

Aula 20 - 18/05 - Ambigüidade.

Aula 21 - 20/05 - Simplificação de gramáticas livres de contexto.

Aula 22 - 25/05 - Revisão de provas. Distribuição de projetos. Formas normais para GLCs. Autômatos de pilha.

Aula 23 - 27/05 - Autômatos de pilha. Exercícios.

Aula 24 - 01/06 - APD pilha vazia X APD estado final. Propriedade do prefixo. Equivalência APN pilha vazia X APN estado final.

Aula 25 - 10/06 - (3hs) - Apresentação dos projetos.

Aula 26 - 17/06 - (3hs) - Equivalência AP X GLC. Pumping Lemma para as LLCs.

Aula 27 - 22/06 - LLCs não-determinísticas. Propriedades de fechamento. Questões decidíveis. Linguagens e gramáticas sensíveis ao contexto.

Aula 28 - 29/06 - Máquinas de Turing com fita limitada. Hierarquia de Chomsky. Conclusões e próximos passos.

Aula 29 - 01/07 - Prova 2.

06/07 - Prova final.