Análise comparativa de algoritmos de conversão de autômatos: powerset vs. subset construction

Abstract

This study investigates the computational complexity of converting nondeterministic finite automata (NFA) to deterministic finite automata (DFA), focusing on comparing the Powerset and Subset Construction algorithms. The significance of this research lies in the central role of automata in theoretical computer science and their practical applications, such as language processing and formal system analysis. The primary objective is to evaluate the efficiency and complexity of both methods, identifying their respective strengths and weaknesses in terms of performance and applicability. The motivation stems from optimizing conversion processes in contexts characterized by high complexity and large data volumes. The methodology involves implementing both algorithms, performing simulations across diverse test scenarios, and conducting empirical time and space consumption analyses. This study presents a detailed evaluation of specific cases in which each approach excels, as well as recommendations for practical applications. The results of this work show that the Subset Construction algorithm generally performs better in terms of time, while the Powerset algorithm has advantages in certain simpler graph structures.