Two Induction-Free Constructions For Finite Automata Determinization
Resumo
The standard algorithm to determinize a finite automaton is the subset construction, however its description and the proof of correctness are usually presented separately.We derive the subset construction from the specification of a deterministic automaton by expressing the language recognized by the automaton as a fixed point of a function. We do this in two ways, one based on the right languages of the states, and the other based on the left languages. The derivation based on right languages resembles a derivation made by Kozen using matrix techniques and Kleene algebra. The derivation based on left languages, on the other hand, uses non-linear functions and has no matrix analogue. Our proofs are induction-free and instead we rely on the uniqueness of fixed-points. In summary, we highlight that an algebraic model of an automaton allows an elegant derivations of the subset construction and highlight the duality between the left and right languages of an automaton.
Palavras-chave:
Determinism, Fixed-point, Minimization
Referências
Janusz A. Brzozowski. 1962. Canonical regular expressions and minimal state graphs for definite events. [link]
John Horton. Conway. 1971. Regular algebra and finite machines, [by] J.H. Conway. Chapman and Hall, London.
J. W. de Bakker and Erik de Vink. 1996. Control flow semantics. The MIT Press City: Cambridge, Mass.
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2001. Introduction to automata theory, languages, and computation, 2nd edition. SIGACT News 32, 1 (March 2001), 60–65. DOI: 10.1145/568438.568455
D. Kozen. 1994. A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events. Information and Computation 110, 2 (1994), 366–390. DOI: 10.1006/inco.1994.1037
Jacques Sakarovitch. 2009. Elements of Automata Theory. Cambridge University Press, Cambridge.
Hiroaki Sengoku and Shuzo YAJIMA. 1992. Minimization of nondeterministic finite automata. Master’s thesis, Kyoto University (1992).
Franck van Breugel. 2001. An introduction to metric semantics: operational and denotational models for programming and specification languages. Theoretical Computer Science 258, 1 (2001), 1–98. DOI: 10.1016/S0304-3975(00)00403-5
John Horton. Conway. 1971. Regular algebra and finite machines, [by] J.H. Conway. Chapman and Hall, London.
J. W. de Bakker and Erik de Vink. 1996. Control flow semantics. The MIT Press City: Cambridge, Mass.
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2001. Introduction to automata theory, languages, and computation, 2nd edition. SIGACT News 32, 1 (March 2001), 60–65. DOI: 10.1145/568438.568455
D. Kozen. 1994. A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events. Information and Computation 110, 2 (1994), 366–390. DOI: 10.1006/inco.1994.1037
Jacques Sakarovitch. 2009. Elements of Automata Theory. Cambridge University Press, Cambridge.
Hiroaki Sengoku and Shuzo YAJIMA. 1992. Minimization of nondeterministic finite automata. Master’s thesis, Kyoto University (1992).
Franck van Breugel. 2001. An introduction to metric semantics: operational and denotational models for programming and specification languages. Theoretical Computer Science 258, 1 (2001), 1–98. DOI: 10.1016/S0304-3975(00)00403-5
Publicado
08/09/2026
Como Citar
Ó, Matheus do; GUALANDI, Hugo Musso.
Two Induction-Free Constructions For Finite Automata Determinization. In: SIMPÓSIO BRASILEIRO DE LINGUAGENS DE PROGRAMAÇÃO (SBLP), 30. , 2026, São Paulo/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 173-177.
DOI: https://doi.org/10.5753/sblp.2026.28537.
