Plano de Estudos
Semigrupos, Autómatos e Linguagens (D) SAL-D
Contextos
Groupo: 3_DMat 2016/17 a 2024/25 > 3º Ciclo > Parte Escolar > Optativas > 52_Opção Grupo B > 1º Semestre
Groupo: 3_DMat 2016/17 a 2024/25 > 3º Ciclo > Parte Escolar > Optativas > 50_Opção Grupo A > 1º Semestre
Groupo: 3_DMat 2016/17 a 2024/25 > 3º Ciclo > Parte Escolar > Optativas > 52_Opção Grupo B > 1º Semestre
Groupo: 3_DMat 2016/17 a 2024/25 > 3º Ciclo > Parte Escolar > Optativas > 50_Opção Grupo A > 1º Semestre
Groupo: 3_DMat 2016/17 a 2024/25 > 3º Ciclo > Parte Escolar > Optativas > 52_Opção Grupo B > 2º Semestre
Groupo: 3_DMat 2016/17 a 2024/25 > 3º Ciclo > Parte Escolar > Optativas > 50_Opção Grupo A > 2º Semestre
ECTS
7.5 (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. Nesta disciplina (D) o aluno deverá estudar por si um ou mais tópicos indicados pelo docente e fazer uma exposição oral sobre os mesmos.
Método de Avaliação
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. Exame final. Qualquer aluno poderá ser chamado a fazer um exame oral.
Carga Horária
Carga Horária de Contacto -
Trabalho Autónomo - 168.0
Carga Total -
Bibliografia
Principal
- · J. M. Howie, "Automata and Languages", Clarendon Press, Oxford (1991). · J. M. Howie, "Fundamentals of Semigroup Theory", Oxford University Press (1996). · M. V. Lawson, "Finite Automata", Chapman&Hall/CRC (2004). · J.-E. Pin, "Varieties of Formal Languages", North Oxford, London, and Plenum, New York (1986).: