Sumários
T11: Construções de autómatos.
19 Novembro 2025, 14:00 • Mário João de Jesus Branco
Construção, a partir de autómatos que reconheçam linguagens K e L, de autómatos que reconheçam a intersecção de K e L – demonstração, a complementação de L, o produto de K por L e a estrela de L. Exemplos. Conclusão de que toda a linguagem racional é reconhecível. Equação da forma X = KX + R no semi-anel das linguagens sobre um alfabeto com as operações de união e de produto. Soluções desta equação.
T11: Autómato reduzido e autómato minimal e autómatos para linguagens racionais.
12 Novembro 2025, 14:00 • Mário João de Jesus Branco
Continuação da última aula, com demonstrações. Autómatos que reconheçam o conjunto vazio e uma linguagem formada apenas por uma letra. Construção, a partir de autómatos que reconheçam linguagens K e L, de autómatos que reconheçam a união e a intersecção de K e L.
T11: Autómato reduzido e autómato minimal.
5 Novembro 2025, 14:00 • Mário João de Jesus Branco
Mais um exemplo de cálculo de um autómato reduzido. Morfismo entre autómatos deterministas, completos e acessíveis. Exemplo. Dois resultados: sobrejectividade de um morfismo de autómatos; unicidade dos morfismos entre dois autómatos. Autómato minimal de uma linguagem definido pelos quocientes dessa linguagem (apenas a definição). Autómato que reconhece um quociente esquerdo de uma linguagem L por uma palavra a partir de um autómato determinista e completo que reconheça L. Alguns resultados sobre o autómato minimal de uma linguagem: o autómato minimal de uma linguagem L reconhece L; L é reconhecível se e só se o seu autómato minimal é finito; construção do autómato minimal de uma linguagem L a partir de um autómato determinista, completo e acessível que reconheça L; isomorfismo entre o autómato minimal de uma linguagem L e qualquer autómato reduzido que reconheça L.
T11: Autómatos deterministas e autómatos reduzidos.
29 Outubro 2025, 14:00 • Mário João de Jesus Branco
Revisão da aula anterior e demonstração de um resultaado da aula anterior. Autómato reduzido. Relação de equivalência no conjunto de estados de um autómato que permite definir autómato reduzido e calcular, por passagem ao quociente, um autómato reduzido equivalente a um autómato determinista, completo e acessível dado. Caracterização recursiva desta relação de equivalência à custa de certas relações de equivalência e um número de relações máximo que a dão. Exemplo.
T11: Sem aula.
22 Outubro 2025, 14:00 • Mário João de Jesus Branco
Não houve aula devido à dispensa de aulas para participação no Dia da Investigação e da Inovação da faculdade.