Disciplina Curricular
Semigrupos, Autómatos e Linguagens SAL
Mestrado Bolonha em Matemática - 1_MMat 2010/11
Peso
9.0 (para cálculo da média)
Objectivos
Este curso tem por objectivo apresentar os fundamentos das Teorias das Linguagens Racionais, dos Autómatos Finitos e dos Semigrupos, as quais constituem não só uma importante área dentro da Álgebra mas são também alguns dos principais pilares da Computação Teórica.
Programa
Palavra e linguagem. Linguagem racional. Autómato finito e linguagem reconhecível. Algoritmos para a construção de autómatos que reconheçam uma linguagem descrita na forma de expressão racional. Autómato minimal de uma linguagem. Equivalência entre as linguagens reconhecíveis e as racionais - Teorema de Kleene. Reconhecimento algébrico de linguagens. Semigrupo sintáctico. Semigrupos, incluindo semigrupos ciclícos, relações de Green, semigrupos aperiódicos, semigrupos finitos simples e 0-simples. Classificação de linguagens racionais e de semigrupos finitos: Teorema de Eilenberg. Teorema de Birkhoff e Teorema de Reiterman.
Métodos de ensino e avaliação
Métodos de ensino: O ensino é composto de aulas teóricas e de aulas teórico-práticas (TP). As aulas teóricas são apresentadas no quadro, dando tempo a que os alunos absorvam os novos conceitos apresentados. As TP são dedicadas à resolução e discussão de problemas. Avaliação: Apresentação de trabalhos e exame final, eventualmente seguido de exame oral.