Linguagens Formais e Autômatos
Período letivo 2010.1:
Atenção para o calendário de final de semestre:
Material didático:
Slides:
Avaliações:
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.