Uma prova do algoritmo de Brzozowski via álgebras de Kleene

Tiburcio, Matheus do Ó Santos

Please use this identifier to cite or link to this item:


			http://hdl.handle.net/11422/29128

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	Gualandi, Hugo Musso	-
dc.contributor.author	Tiburcio, Matheus do Ó Santos	-
dc.date.accessioned	2026-05-04T12:52:36Z	-
dc.date.available	2026-05-16T03:09:01Z	-
dc.date.issued	2026-02-11	-
dc.identifier.uri	http://hdl.handle.net/11422/29128	-
dc.language	por	pt_BR
dc.publisher	Universidade Federal do Rio de Janeiro	pt_BR
dc.rights	Acesso Aberto	pt_BR
dc.subject	Linguagens regulares	pt_BR
dc.subject	Álgebra de Kleene	pt_BR
dc.subject	Autômatos finitos	pt_BR
dc.subject	Minimização de autômatos finitos	pt_BR
dc.subject	Algoritmo de Brzozowski	pt_BR
dc.subject	Regular languages	pt_BR
dc.subject	Kleene algebra	pt_BR
dc.subject	Finite automata	pt_BR
dc.subject	Finite automata minimization	pt_BR
dc.subject	Brzozowski’s algorithm	pt_BR
dc.title	Uma prova do algoritmo de Brzozowski via álgebras de Kleene	pt_BR
dc.type	Trabalho de conclusão de graduação	pt_BR
dc.contributor.advisorCo1	Paixão, João Antonio Recio da	-
dc.contributor.referee1	Coutinho, Severino Collier	-
dc.contributor.referee2	Adauto, Matheus Nunes	-
dc.description.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.	pt_BR
dc.publisher.country	Brasil	pt_BR
dc.publisher.department	Instituto de Computação	pt_BR
dc.publisher.initials	UFRJ	pt_BR
dc.subject.cnpq	CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO	pt_BR
dc.embargo.terms	aberto	pt_BR
Appears in Collections:	Ciência da Computação

Files in This Item:

File	Description	Size	Format
MÓSTiburcio.pdf		496.86 kB	Adobe PDF	View/Open

Show simple item record Recommend this item View Statistics

Pantheon Institutional repository