Linguagens Formais e Autômatos
- Semestre: 2010.2
- Professor: Guilherme Dias da Fonseca
- Horário: 2as e 4as de 20 às 22h
- Veja a página do curso no moodle.
O estudo de linguagens formais e autômatos precede a existência dos primeiros computadores. Iniciado nas áreas de matemática, linguística e biologia, este estudo veio a se tornar o pilar central da teoria da computação. Após décadas de pesquisa no assunto, os tópicos fundamentais já se encontram bastante estáveis. Porém, a gama de aplicações da teoria dos autômatos e linguagens formais é cada dia maior, de modo que é impossível um bom profissional de computação não ter estudado esta matéria. Este curso tem uma abordagem prática, aonde os resultados teóricos são apresentados junto com aplicações em diversas áreas.
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
- Autômatos de Pilha
- Parsing
- Máquinas de Turing
- Computabilidade
- Complexidade
Bibliografia
Não usaremos nenhum livro texto. Porém vou listar abaixo algumas possíveis referências. Notem que há sempre pequenas diferenças de notação e definições de um texto para outro. Nas provas você deve entender e utilizar as notações e definições vistas em sala. De um modo geral, o curso terá um foco prático e moderno, sem os formalismos que eram comuns nos livros mais antigos sobre o assunto.
- Introduction to Automata Theory, Languages and Computation. J. E. Hopcroft, R. Motwani, J. D. Ullman. Atualmente na terceira edição. A segunda edição tem uma versão em português. A primeira edição não é muito boa para este curso.
- An Introduction to Formal Languages and Automata. P. Linz.
Avaliação
O curso terá 3 provas e trabalhos de implementação. Todos os trabalhos serão convertidos em uma única nota. A média do curso será a média aritmética das 3 maiores notas, dentre o total de 4 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: Matéria até gramáticas regulares.
- Prova 2: Matéria a partir de gramáticas regulares.
- Prova 3: Toda a matéria.
- Trabalhos durante o curso formarão uma nota.
Além dessas notas, o aluno pode ganhar até um ponto na média final contribuindo para o wiki do curso.
Cronograma
- 23/08: Alfabetos, strings, linguagens e operações entre eles.
- 25/08: Expressões regulares formais.
- 30/08: Exercícios de expressões regulares.
- 01/09: Expressões regulares computacionais.
- 06/09: Não haverá aula.
- 08/09: Não haverá aula.
- 13/09: Programa com expressões regulares.
- 15/09: Autômatos finitos.
- 20/09: Conversão AFND -> AFD.
- 22/09: Conversão ER -> AFND.
- 27/09: Conversão AFD -> ER.
- 29/09: Propriedades das linguages regulares.
- 04/10: Gramáticas e hierarquia de Chomsky.
- 06/10: Revisão.
- 13/10: Prova.
- 18/10: Gramáticas livre de contexto.
- 20/10: Gramáticas para linguagens de programação.
- 25/10: Operadores, precedência e associatividade.
- 27/10: Parser de descida recursiva.
- 03/11: Gramáticas sensíveis ao contexto.
- 08/11: Máquinas de Turing.
- 10/11: Computabilidade e tese de Church.
- 17/11: Problemas NP-Completos.
- 29/11: Revisão.
- 01/12: Prova.
- 06/12: Prova.