Semigrupos, Autómatos e Linguagens
Código
10833
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
1
Total de horas
15
Língua de ensino
Português
Objectivos
Fornecer uma introdução básica à Teoria dos Semigrupos, efetuar um estudo elementar, matematicamente rigoroso, de alguns tópicos da Teoria da Computação, nomeadamente dos Autómatos Finitos e das Linguagens Regulares, e ainda estabelecer as pontes que interligam estas duas áreas do conhecimento.
Conteúdo
1. Generalidades
2. Relações de Green e Regularidade
3. O sistema computacional GAP
4. Semigrupos 0-simples. O Teorema de Rees
5. Semigrupos inversos: uma breve introdução
6. Linguagens. Linguagens Racionais
7. Gramáticas: uma breve introdução. Gramáticas Regulares
8. Autómatos Finitos
9. Monóide de Transições e Monóide Sintáctico
10. Variedades de semigrupos e de linguagens: uma breve introdução
Bibliografia
1. J.M. Howie, Automata and Languages, Oxford Univ. Press, 1991.
2. J.M. Howie, Fundamentals of semigroup theory, Oxford Univ. Press, 1995.
3. J.E. Pin, Varieties of formal languages, Plenum, 1986.
4. M.V. Lawson, Finite Automata, Chapman & Hall/CRC, 2003.
5. The GAP Group, GAP - Groups, Algorithms, and Programming,
2008, http://www.gap-system.org.
Método de ensino
Aulas teórico-práticas participadas, com exposição oral de matéria e resolução de problemas.
Método de avaliação
Avaliação contínua: uma vez que há apenas dois alunos inscritos e a disciplina funciona em regime tutorial, o método de avaliação contínua foi acordado com os alunos.
Exame Final: se a nota do exame final for superior ou igual a 16,5 (valores), o aluno tem de efetuar uma prova extra.