Tópicos de Teoria da Computação
Código
9648
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Matemática
Créditos
6.0
Professor responsável
Vitor Hugo Bento Dias Fernandes
Horas semanais
4
Total de horas
56
Língua de ensino
Português
Objectivos
Pretende-se estudar diversas classes de linguagens formais (em particular as da hierarquia de Chomsky: regulares, independentes de contexto, sensíveis ao contexto e recursivamente enumeráveis) e as estruturas finitas (gramáticas e máquinas) que as geram ou reconhecem.
Pré-requisitos
-
Conteúdo
1. Linguagens reconhecíveis e linguagens racionais: autómatos; autómatos não determinísticos e autómatos incompletos; linguagens racionais; o Teorema de Kleene; congruências sintácticas; autómatos minimais; monóide de transições e monóide sintáctico de um autómato.
2. A hierarquia de Chomsky: gramáticas; linguagens regulares; linguagens independentes de contexto; Forma Normal de Chomsky; autómatos de pilha; linguagens sensíveis ao contexto; máquinas de Turing; modificações de Máquinas de Turing; a tese de Church; máquinas versus gramáticas; a hierarquia de Chomsky.
3. Problemas de decidibilidade: a indecidibilidade do problema da correspondência de Post e outros problemas de indecidibilidade.
Bibliografia
1. M. Sipser, "Introduction to the Theory of Computation", Thomson, 2006.
2. J.E. Hopcroft e J.D. Ullman, “Introduction to Automata Theory, Languages and Computation”, Addison Wesley, 1979.
3. D.C. Kozen, “Automata and Computability”, Springer, 1997.
4. M. Delgado, "Teoria Algébrica dos Autómatos, FCUP, 2001
5. J.E. Pin, “Varieties of Formal Languages”, Plenum, New-York, 1986.
Método de ensino
Aulas teórico-práticas participadas, com exposição oral de matéria e resolução deproblemas.
No caso de o número de alunos ser inferior a 5, as aulas serão em regime tutorial. O aluno prepara o conteúdo de cada capítulo seguindo a bibliografia específica indicada para tal e resolve exercícios. Nas sessões de contacto serão discutidas questões sobre a matéria estudada, esclarecidas dúvidas e corrigidos os exercícios.
Método de avaliação
Avaliação contínua: 3 grupos de problemas para resolver (40%+40%+20%). Alunos podem ser obrigados a fazer uma apresentação oral (com discussão) de suas soluções.