Sumários
T11: Autómatos e linguagens reconhecíveis.
15 Outubro 2025, 14:00 • Mário João de Jesus Branco
Exemplo de aplicação do Lema da Estrela para linguagens reconhecíveis. Autómato determinista e autómato não determinista. Relativamente a um autómato determinista, função de transição e extensão da função de transição a palavras. Exemplo. Autómato completo, acessível e coacessível. Autómatos equivalentes. Algoritmos para passar de um autómato dado a um autómato que lhe seja equivalente e que seja: acessível e coacessível; completo; determinista (autómato das partes); determinista, completo e acessível. Exemplos.
Linguagens racionais e autómatos.
8 Outubro 2025, 14:00 • Mário João de Jesus Branco
Revisão da última aula e demonstração do último resultado. Breve introdução sobre o surgimento dos autómatos finitos. Autómato e autómato finito. Exemplo. Diagrama de estado de um autómato. Transições consecutivas e caminho. Origem, extremidade, comprimento e etiqueta de um caminho. Caminho de comprimento zero. Caminho bem sucedido. Palavra reconhecida por um autómato. Linguagem reconhecida por um autómato. Exemplos. Linguagem reconhecível. Lema da Estrela para linguagens reconhecíveis.
Linguagens racionais.
1 Outubro 2025, 14:00 • Mário João de Jesus Branco
Algumas operações sobre linguagens: operações booleanas, produto, fecho positivo, fecho e quocientes esquerdo e direito. Exemplos. Linguagem racional e expressão racional. Exemplos. Algumas propriedades do conjunto das linguagens racionais. Reverso de uma linguagem. Proposição (demonstração como exercício): o conjunto das linguagens racionais é fechado para a operação de reverso.
Semigrupo livre e linguagens formais: introdução.
24 Setembro 2025, 14:00 • Mário João de Jesus Branco
Breve introdução sobre o surgimento das linguagens formais. Alfabeto, letra, palavra, semigrupo livre e monoide livre. Propriedade universal do semigrupo livre. Semigrupos como quocientes de semigrupos livres. Linguagem formal. Conteúdo, comprimento, prefixo, sufixo, factor, subpalavra e reverso de uma palavra. Exemplos.
Noções básicas de semigrupos.
17 Setembro 2025, 14:00 • Mário João de Jesus Branco
Ideal esquerdo, ideal direito e ideal (bilateral) de um semigrupo. Exemplos. Morfismo de semigrupos e morfismo de monoides. Congruência de um semigrupo. Congruência de Rees, congruência sintáctica. Semigrupo quociente. Semigrupo de Rees e semigrupo sintáctico. Teorema do homomorfismo para semigrupos (e monoides). Produto directo de uma família arbitrária de semigrupos. Semigrupo de transformações. Representação de qualquer semigrupo como semigrupo de transformações.