Sumários

T11: Aula extraordinária. Noções e resultados básicos da teoria dos semigrupos.

18 Dezembro 2025, 10:00 • Mário João de Jesus Branco

(Aula leccionada remotamente.)
Morfismo sobrejectivo entre semigrupos finitos e idempotentes e elementos regulares. Relações de Green. Comutatividade entre as relações R e L. Exemplos. Igualdade entre J e D num semigrupo finito. Estrutura de uma D-classe em termos de R-classes e L-classes.

T11: Aula extraordinária. Linguagens livres de estrela e introdução à teoria dos semigrupos.

11 Dezembro 2025, 17:00 • Mário João de Jesus Branco

(Aula leccionada remotamente.)
Linguagem livre de estrela e Teorema de Schützenberger sobre linguagens livres de estrela (sem demonstração). Exemplos. Estrutura dos semigrupos cíclicos, elementos idempotentes em semigrupos finitos, elemento regular e semigrupo inverso.

T11: Sem aula (reunião do Conselho de Escola).

10 Dezembro 2025, 14:00 • Mário João de Jesus Branco

Não houve aula devido à realização de uma reunião do Conselho de Escola com início às 14h.

T11: Reconhecibilidade de linguagens por monoides.

3 Dezembro 2025, 14:00 • Mário João de Jesus Branco

Reconhecibilidade de uma linguagem por um morfismo e reconhecibilidade de uma linguagem por um monoide. Exemplos. Resultado: o morfismo canónico para o monoide de transição de um autómato reconhece a linguagem reconhecida pelo autómato. Construção, a partir de um morfismo que reconheça uma linguagem L, de um autómato que reconheça L. Exemplo. Conclusão de que uma linguagem é reconhecida por um autómato (finito) se e só se é reconhecida por um monoide (finito). Monoide de transição do autómato minimal de uma linguagem L - monoide sintáctico e morfismo sintáctico de L. Conclusão de que o morfismo sintáctico de uma linguagem a reconhece; e de que uma linguagem é reconhecível se e só se o seu monoide sintáctico é finito. Divisão de monoides. Transitividade da divisão de monoides. Monoide sintáctico de uma linguagem. Relação entre reconhecibilidade de uma linguagem e finitude do monoide sintáctico. Alguns resultados.

T11: Teorema de Kleene.

26 Novembro 2025, 14:00 • Mário João de Jesus Branco

Sistema de equações sobre aquele semi-anel que generaliza a equação anterior. Unicidade e resolução do sistema no caso em que a palavra vazia não pertence a nenhum dos coeficientes das variáveis. Conclusão de que as componentes da solução do sistema são racionais se cada uma das linguagens intervenientes no sistema o forem. Exemplo. Determinação da linguagem reconhecida por um autómato finito através da resolução de um sistema de equações. Exemplo. Conclusão de que toda a linguagem reconhecível é racional. Conclusão de que as linguagens reconhecíveis são precisamente as linguagens racionais (Teorema de Kleene) e de que, como consequência, as linguagens racionais são fechadas para as operações de intersecção e de complementação. Monoide de transição de um autómato qualquer. Exemplos.