Plano de Estudos

Semigrupos, Autómatos e Linguagens SAL

Contextos

ECTS

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étodo de 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.

Carga Horária

Bibliografia

Principal

• Automata and Languages: J. M. Howie Clarendon Press, Oxford (1991)
• An Introduction to Semigroup Theory: J. M. Howie Academic Press, London (1976)
• Finite Automata: M. V. Lawson Chapman & Hall/CRC (2004)
• Varieties of Formal Languages: J. E. Pin North Oxford, London, and Plenum, New York (1986)
• Universal Algebra for Computer Scientists: W. Wechler Springer-Verlag, Berlin (1992)

Secundária

• Introduction to Automata Theory, Languages and Computation: J. E. Hopcroft, R. Motwani e J. D. Ullman Addison-Wesley Publ. Co., Massachusetts (várias edições)
• Introduction to Automata Theory, Languages and Computation: J. E. Hopcroft e J. D. Ullman Addison-Wesley Publ. Co., Massachusetts (1979)
• Finite Semigroups and Universal Algebra: J. Almeida World Scientific, Singapore (1994)
• Handbook of Formal Languages, Vol. 1: G. Rozenbeg e A. Salomaa (Eds.) Springer-Verlag, Berlin (1997)

Disciplinas de Execução

2019/2020 - 1 Semestre

2017/2018 - 2 Semestre

2021/2022 - 1 Semestre

2016/2017 - 1 Semestre