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.