CONCATENATION AND KLEENE STAR ON DETERMINISTIC FINITE AUTOMATA
Guo‐Qiang Zhang, Xiangnan Zhou, Robert Fraser, LICONG CUI · 2012
Abstract—This paper presents direct, explicit algebraic constructions of concatenation and Kleene star on deterministic finite automata (DFA), using the Boolean-matrix method of Zhang [5] and ideas of Kozen [2]. The consequence is trifold: (1) it provides an alternative proof of the classical Kleene’s Theorem on the equivalence of regular expressions and DFAs without using nondeterministic finite automata (NFA); (2) it demonstrates how the language constructions of concatenation and Kleene star can be captured elegantly as algebraic laws in the form of “binomial theorems; ” (3) it provides a demonstration of the (tight) upper bounds of the state complexity of concatenation and Kleene star, but offers a way to study the state complexity of NFA also. I. MATRIX-APPROACH TO AUTOMATA THEORY A Boolean matrix is a matrix (of size m×n) whose elements are either 0 or 1, where the internal operations are carried out