Pantheon Repositório Institucional da UFRJ
Coleta, preserva e divulga a produção acadêmica digital em todas as áreas do conhecimento.
São os ativos do repositório, além de teses e dissertações da UFRJ, artigos científicos, livros eletrônicos, capítulos de livros e trabalhos apresentados em eventos por professores, pesquisadores, funcionários administrativos e alunos de mestrado e doutorado.
Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/11422/29128
| Tipo: | Trabalho de conclusão de graduação |
| Título: | Uma prova do algoritmo de Brzozowski via álgebras de Kleene |
| Autor(es)/Inventor(es): | Tiburcio, Matheus do Ó Santos |
| Orientador: | Gualandi, Hugo Musso |
| Coorientador: | Paixão, João Antonio Recio da |
| Resumo: | Autômatos finitos são objetos recursivamente definidos, o que torna natural provarmos suas propriedades através de indução. Em especial, muitos problemas de teoria dos autômatos necessitam de identificar se dois autômatos diferentes têm a mesma linguagem, isto é, se são equivalentes. Tais provas geralmente são feitas através de indução no comprimento dos caminhos, além de serem feitas em duas direções, visto que precisamos mostrar que todo caminho válido em um autômato tem um equivalente noutro e vice-versa. Estas provas apresentam dois problemas principais: uma escolha ruim de caso base e hipótese indutiva pode tornar provas por indução desnecessariamente complicadas ou até incorretas; provas de ida-e-volta podem ser desafiadoras e, neste contexto, cada caminho do autômato precisa ter seu equivalente encontrado em um autômato diferente. Uma alternativa para ambos problemas é o teorema da fusão, que torna provas indutivas em provas por igualdade, simplificando-as e removendo preocupações herdadas de provas indutivas. Neste trabalho, buscamos demonstrar como álgebras de Kleene e o teorema da fusão podem conversar bem com teoria dos autômatos finitos e fazemos isto focando em um problema em específico: minimização de autômatos finitos. Trazemos a primeira prova da corretude do algoritmo de Brzozowski à luz do teorema da fusão e via formalismo matricial. |
| Palavras-chave: | Linguagens regulares Álgebra de Kleene Autômatos finitos Minimização de autômatos finitos Algoritmo de Brzozowski Regular languages Kleene algebra Finite automata Finite automata minimization Brzozowski’s algorithm |
| Assunto CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Unidade produtora: | Instituto de Computação |
| Editora: | Universidade Federal do Rio de Janeiro |
| Data de publicação: | 11-Fev-2026 |
| País de publicação: | Brasil |
| Idioma da publicação: | por |
| Tipo de acesso: | Acesso Aberto |
| Aparece nas coleções: | Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| MÓSTiburcio.pdf | 496.86 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.