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
Alan James Cain, Vitor Hugo Bento Dias Fernandes
Horas semanais
4
Total de horas
56
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.
Pré-requisitos
Teoria elementar de grupos: subgrupos, coclasses, grupos quocientes, homomorfismos.
Conteúdo
1. Generalidades
2. Relações de Green
3. Semigrupos regulares, incluindo semigrupos 0-simples e a teorema de Rees-Suschkewitsch
4. Semigrupos inversos: uma breve introdução
5. Linguagens. Linguagens Racionais e Autómatos Finitos
6. Gramáticas: uma breve introdução. Gramáticas Regulares
7. Monóide de Transições e Monóide Sintáctico
8. Pseudovariedades de semigrupos e de variedades de linguagens racionais: 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.
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 (cado grupo é 1/3 da nota final).