Plano de Estudos
Semigrupos, Autómatos e Linguagens SAL
Contextos
Groupo: 2_MMat 2022/23 > 2º Ciclo > Parte Escolar > Opcionais > 2º Ano > 689_Opcionais Área CMat / 2º Ano
Groupo: 2_MMat 2022/23 > 2º Ciclo > Parte Escolar > Opcionais > 1º Ano > 688_Opcionais Área CMat / 1º Ano > 1º Semestre
Groupo: 2_MMat 2022/23 > 2º Ciclo > Parte Escolar > Opcionais > 2º Ano > 689_Opcionais Área CMat / 2º Ano
Groupo: 2_MMat 2022/23 > 2º Ciclo > Parte Escolar > Opcionais > 1º Ano > 688_Opcionais Área CMat / 1º Ano > 1º Semestre
ECTS
6.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ór
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étodo de Avaliação
Apresentação de trabalhos e exame final, eventualmente seguido de exame oral
Carga Horária
Carga Horária de Contacto -
Trabalho Autónomo - 133.0
Carga Total -
Bibliografia
Principal
- Automata and Languages: J. M. Howie 1991 Clarendon Press, Oxford
- An Introduction to Semigroup Theory: J. M. Howie 1976 Academic Press, London
- Finite Automata: M. V. Lawson 2004 Chapman & Hall/CRC
- Varieties of Formal Languages: J. E. Pin 1986 North Oxford, London, and Plenum, New York
- Universal Algebra for Computer Scientists: W. Wechler 1992 Springer-Verlag, Berlin
Secundária
- Introduction to Automata Theory, Languages and Computation: J. E. Hopcroft, R. Motwani e J. D. Ullman N/A Addison-Wesley Publ. Co., Massachusetts (várias edições)
- Introduction to Automata Theory, Languages and Computation: J. E. Hopcroft e J. D. Ullman 1979 Addison-Wesley Publ. Co., Massachusetts
- Finite Semigroups and Universal Algebra: J. Almeida 1994 World Scientific, Singapore
- Handbook of Formal Languages, Vol. 1: G. Rozenbeg e A. Salomaa (Eds.) 1997 Springer-Verlag, Berlin