Linguagens Formais e Autômatos
Programa do Curso
- Alfabetos e linguagens
- Expressões regulares
- Autômatos finitos determinísticos
- Autômatos finitos não determinísticos
- Gramáticas
- Hierarquia de Chomsky
- Gramáticas Livre de Contexto
- Parsing
- Máquinas de Turing
- Computabilidade
Não usaremos nenhum livro, slides ou apostila. É recomendado que os alunos contribuam com anotações através do wiki do curso.
Avaliação
O curso terá 3 provas e 2 trabalhos. A média do curso será a média aritmética das 4 maiores notas. Não haverá prova final nem segunda chamada (salvo nos casos em que leis ou normas da Unirio obriguem o contrário).
- Prova 1 dia 18/05: Matéria até gramáticas regulares.
- Prova 2 dia 24/06 (Nova data!): Matéria a partir de gramáticas regulares.
- Prova 3 dia 06/07: Toda a matéria.
- Trabalho 1 dia 10/05: Implementação usando expressões regulares.
- Trabalho 2 dia 21/06: Implementação de um parser.
Além dessas notas, o aluno pode ganhar até um ponto na média final contribuindo para o wiki do curso.
Cronograma
- 15/03: Alfabetos, strings, linguagens e operações entre eles.
- 17/03: Expressões regulares formais.
- 08/04: Exercícios de expressões regulares.
- 13/04: Expressões regulares computacionais.
- 15/04: Programa com expressões regulares.
- 20/04: Autômatos finitos.
- 27/04: Conversão AFND -> AFD.
- 29/04: Conversão ER -> AFND.
- 04/05: Conversão AFD -> ER.
- 06/05: Propriedades das linguages regulares.
- 11/05: Gramáticas e hierarquia de Chomsky.
- 13/05: Correção da pseudo-prova.
- 18/05: Prova.
- 20/05: Gramáticas livre de contexto.
- 25/05: Parser recursivo.
- 27/05: Exercícios de GLC.
- 01/06: Gramáticas sensíveis ao contexto.
- 08/06: Máquinas de Turing.
- 10/06: Computabilidade e tese de Church.
- 17/06: Problemas NP-Completos.
- 22/06: Revisão
- 24/06: Prova.
- 06/07: Prova.