Directly constructing a DFA for the Kleene star of a language given as a DFA?

Question

The regular languages are closed under Kleene star. One common way to prove this is to define a construction that, given a DFA or NFA for a regular language $L$, produces a new NFA whose language is $L^\star$. The resulting automaton uses $\varepsilon$-transitions and thus is only an NFA, not a DFA.

I’ve taught this construction for years in my intro theory class. It’s a great motivation for why NFAs are useful tools. But I’ve been wondering whether there’s an alternative way to show this that purely relies on DFAs. Specifically, given a DFA for a regular language $L$, is there a direct construction that produces a new DFA for $L^\star$?

I say “direct construction” here because it’s certainly possible to build a DFA for $L^\star$ by first building an NFA for $L^\star$ and then using the subset construction to turn it into a DFA. I’m interested specifically in a way to go from the input DFA to the output DFA without routing through NFA space.

Answer 1

Let $L$ be a regular language of $A^*$. It might be difficult to prove there is no "direct construction" for the DFA of $L^*$, but in any case, the complexity will remain exponential. Indeed, as shown in [2], for every $n \geqslant 2$, there is a language $L$ of state complexity $n$ such that $L^*$ is of state complexity $3 \cdot 2^{n-2}$. About these complexity questions, you might be interested in the nice comprehensive survey [1] in the Handbook of automata theory.

However, a simple direct construction is possible if $L$ is a prefix code, that is, if $L$ is a set of nonempty words in which any two distinct words are incomparable for the prefix order. In this case, you can define the automaton ${\cal A} = (P, A, \cdot, 1, 1)$, where $P$ is the set of prefixes of the words of $L$ and the transition function is defined, for all $p\in P$ and $a\in A$, by $$ p\cdot a = \begin{cases} pa &\text{if } pa\in P - L,\\ 1 &\text{if } pa\in L\\ \emptyset &\text{otherwise} \end{cases} $$ This automaton recognises $L^*$. To get the minimal DFA of $L^*$, one can identify the states $u$ and $v$ such that $u^{-1}L^* = v^{-1}L^*$. In practice, the first step is to label by $1$ the root and the leaves of the tree representing $L$. Then the remaining nodes are numbered by assigning the same number to the nodes $u$ and $v$ such as the subtrees rooted in $u$ and $v$ are equal. This works even for infinite regular prefix codes, as shown in the example below.

Let $L = a(ba)^*a$. It is easy to see that $L$ is a prefix code, represented by the tree

$\hskip 70pt$

After labelling the tree

$\hskip 50pt$

One gets the minimal automaton of $(a(ba)^*a)^*$.

$\hskip 95pt$

[1] Gruber, Hermann; Holzer, Markus; Kutrib, Martin. Descriptional complexity of regular languages. Handbook of automata theory. Vol. I. Theoretical foundations, 411-457, EMS Press, Berlin, (2021)

[2] Yu, Sheng; Zhuang, Qingyu; Salomaa, Kai. The state complexities of some basic operations on regular languages. Theoret. Comput. Sci. 125 (1994), no. 2, 315-328.