We prove that the automaton presented by Maslov [Soviet Math. Doklady 11, 1373-1375 (1970)] meets the upper bound 3/4 · 2n on the state complexity of Kleene closure. This fixes a small error in this paper that claimed the upper bound 3/4 · 2n − 1. Our main result shows that the upper bounds 2n−1 + 2n−1−k on the state complexity of Kleene closure of a language accepted by an n-state DFA with k final states are tight for every k in the binary case. We also present some results of our calculations. We consider not only the worst case, but we study all possible values that can be obtained as the state complexity of Kleene closure of a regular language accepted by a minimal n-state DFA. Using the lists of pairwise non-isomorphic binary automata of 2,3,4, and 5 states, we compute the frequencies of the resulting complexities for Kleene closure, and show that every value in the range from 1 to 3/4 · 2n occurs at least ones. In the case of n = 6, 7, 8, we change the strategy, and consider binary automata, in which the first symbol is a circular shift of the states, and the second symbol is generated randomly. We show that all values from 1 to 3/4 · 2n are attainable, that is, for every m with 1 ≤ m ≤ 3/4 · 2n, there exists an nstate binary DFA A such that the state complexity of L(A)∗ is exactly m.
Kleene closure is a basic operation on formal languages which is defined as
L∗ = { w | w = v1v2 · · · vk, k ≥ 0, vi ∈ L for all i} .
It is known that if L is recognized by an n-state
deterministic finite automaton (DFA), then the language L∗ is
recognized by a DFA of at most 3/4 · 2n states [
Later, Yu, Zhuang, and Salomaa [
∗Research supported by grants VEGA 2/0183/11, APVV-0035-10. † Research supported by grants VEGA 2/0183/11, APVV-0035-10.
In this paper we give a proof of Maslov’s result and we
fix an error in his paper [
In the second part of our paper we consider not only the worst case, but rather study all possible values that can be obtained as the number of states of the minimal DFA recognizing the Kleene closure of a regular language represented by a minimal n-state DFA. The problem is known as "the magic number problem" in the literature, and so called "magic numbers" are exactly the "holes" in the hierarchy that cannot be obtained in such a way.
The problem was first stated for NFA to DFA conversion
by Iwama, Kambayashi, and Takaki in [
For Kleene closure, the possible resulting vales are in
the range from 1 to 3/4 · 2n, for an alphabet of at least
two symbols, and in the range from 1 to (n − 1)2 + 1 for a
unary alphabet, and it is known that for a growing alphabet
of size 2n, no magic numbers exist [
Here we study the binary case. Using the lists of pairwise non-isomorphic automata of 2,3,4, and 5 states, we compute the frequencies of the resulting complexities for Kleene closure, and show that every value in the range from 1 to 3/4 · 2n occurs at least ones. We display our results in graphs, and compute the average complexity.
In the case of n = 6, 7, 8, we change the strategy, and consider binary automata, in which the first symbol is a circular shift of the states, and the second symbol is generated randomly. We consider an arbitrary number of final states. We show that all values from 1 to 3/4 · 2n are attainable, and we show that for every m with 1 ≤ m ≤ 3/4 · 2n, there exists an n-state binary DFA A such that the state complexity of L(A)∗ is exactly m.
Thus our calculations show, that in the binary case, up
to n = 8, no magic numbers exists. Moreover, for every n,
the numbers 1, n, and 2n−1 + 2n−1−k with 1 ≤ k ≤ n − 1 are
attainable by the complexity of Kleene closure. The
situation is completely different in the case of a unary alphabet,
where two holes of length n exist for every n [
Let Σ be a finite alphabet and Σ∗ the set of all strings over Σ. The empty string is denoted by ε . The length of a string w is | w| . A language is any subset of Σ∗. We denote the size of a set A by | A| , and its power-set by 2A.
A deterministic finite state automaton is a quintuple A = (Q, Σ,δ , s, F ), where Q is a finite set of states; Σ is a finite set of input symbols; δ is the transition function that takes as arguments a state and an input symbol and returns a state; s is an element of Q called the initial state; F is the set of final states (or accepting states), F ⊆ Q. The language accepted or recognized by the DFA A is defined as the set L(A) = { w ∈ Σ∗ | δ (s, w) ∈ F } .
A nondeterministic finite automaton is a quintuple A = (Q, Σ,δ , s, F ), where Q, Σ, s, and F are the same as for a DFA, and δ is the transition function that takes a state in Q and an input symbol in Σ as arguments and returns a subset of Q. The language accepted or recognized by the NFA A is defined as the set L(A) = { w ∈ Σ∗ | δ (s, w) ∩ F 6= 0/} .
Two automata are equivalent if they recognize the same language.
A DFA A is minimal if every equivalent DFA has at least as many states as A. It is known that every regular language has a unique, up to isomorphism, minimal DFA, and that a DFA A = (Q, Σ,δ , s, F ) is minimal if an only if (i) all its states are reachable, that is, for every state q in Q, where exists a string w in Σ∗ such that δ (s, w) = q; and (ii) no two distinct states are equivalent; two states p and q are equivalent if for every string w in Σ∗, δ (p, w) ∈ F if and only if δ (q, w) ∈ F.
The state complexity of a regular language L, denoted by sc(L), is number of states in the minimal DFA accepting the language L.
Every NFA can be converted to an equivalent DFA
by the subset construction [
To prove that states of a DFA are not equivalent, we will use the following observation.
Proposition 1. Let N be an NFA. Let for every state q of the NFA N, there exists a string wq such that wq is accepted by N only from the state q. Then the subset automaton corresponding to the NFA N does not have equivalent states. Proof. Let S, T be subsets of states of N, where S 6= T . Without loss of generality, there exists a state q such that q ∈ S and q ∈/ T . Then the string wq is accepted from S but wq is not from T . Hence S and T are not equivalent.
For languages K and L the concatenation K · L is defined as K · L = { uv | u ∈ K, v ∈ L} . The language Lk with k ≥ 0 is defined inductively by L0 = { ε } , L1 = L, Li+1 = Li · L. Definition 1. The Kleene closure of a language L is the language L∗ defined as
L∗ = [ Li.
i≥0 3
In this section we describe the construction of a nondeterministic automaton recognizing the Kleene closure of a given language reprezented by DFA.
Let A = (Q, Σ,δ , s, F ) be the minimal DFA accepting a language L. Construct an NFA A∗ for the language L∗ from DFA A as follows: • For each state q in Q and each symbol a in Σ such that
δ (q, a) ∈ F, add the transition on a from q to s. • If s ∈/ F , then add a new start state q0 to Q and make this state accepting. For each symbol a in Σ add the transition on a from q0 to δ (s, a) if δ (s, a) ∈/ F , and from q0 to δ (s, a) and from q0 to s if δ (s, a) ∈ F.
We illustrate this construction in the following example.
Example 1. Consider the DFA A shown in Fig. 1. In Fig. 2, we add the following transitions: the transition from s to the state s on the letter b because A has the transition from s to the final state 2; the transition from 1 to s on a because A has the transition from 1 to the final state 2; the transition from 2 to s on b because A has the transition from 2 to the final state 2.
Since s is non-final, we add the new initial state q0, make this state final, and we add transitions from q0 as follows Since there is a transition from the old initial state s to state 1 on the letter a in A, and 1 is non-final, we add the new transition from the state q0 to 1 on a, and since there is transition from s to the state 2, which is final in A, we add the new transition from state q0 to 2 and transition from q0 to s on the letter b.
Yu, Zhuang, and Salomaa [
The first witness language was presented already by
Maslov [
Here we fix this error and provide a proof.
0 1 2 n−3 n−2
n−1
First, construct an NFA N for the language L(A)∗ by
adding the transition on a from n − 2 to 0, by adding a new
initial and final state q0, and by adding the transition on a
from q0 to 1 and the transition on b from q0 to 0. The NFA
N is shown in Fig. 5.
The state complexity of Kleene closure is defined as the
minimal number of states that are sufficient and necessary
in the worst case for a DFA to accept the Kleene closure
of a regular language represented by an n-state DFA. The
following upper bound is from [
Lemma 1 (Upper Bound [
Proof. Construct the NFA N for the language L(A)∗ as described above. Consider the subset automaton of the NFA N. Let S be a reachable subset of automaton. Notice that if a final state of N is in S, than the state s is also in S. It follows that only the following subsets can be reachable in the subset automaton: 1. { q0} ; 2. S ⊆ Q with s ∈ S, 3. S ⊆ Q \ (F ∪ { s} ) and S 6= 0/.
This gives at most 1 + 2n−1 + 2n−1−k − 1 reachable sets, which gives the desired upper bound.
Notice that the number 2n−1 + 2n−1−k is maximal if k = 1. For k = 1, we have 2n−1 + 2n−1−k = 2n−1 + 2n−2 = 3/4 · 2n. Thus we get the following upper bound.
Corollary 1. Let L a language accepted by an n-state DFA. Then the minimal DFA for the language L∗ has at most 3/4 · 2n states.
The next two lemmata show that the subset automaton of the NFA N has 3/4 · 2n reachable and pairwise distinguishable states.
Lemma 2. The subset automaton of the NFA N shown in Fig. 5 has 3/4 · 2n reachable states.
Proof. By induction on | S| , we prove that every subset S of { 0, 1, . . . , n − 1} , such that n − 1 ∈ S implies 0 ∈ S, is reachable. The base is | S| = 1. The set { q0} is reachable since it is the initial state of the subset automaton. The set { i} , where 0 ≤ i ≤ n − 2, is reached from { q0} by the
b ai string bai since we have { q0} −→ { 0} −→ { i} .
Assume that every set S with | S| = k, where 1 ≤ k ≤ n − 1, is reachable. Let S = { i1, i2, i3, . . . , ik, ik+1} , where 0 ≤ i1 < i2 < · · · < ik < ik+1 ≤ n − 1, be set of size k + 1.
Consider three cases: (i) i1 = 0 and ik+1 = n − 1.
Take S′ = { i2 − 1, i3 − 1, . . . , ik − 1, n − 2} . Then | S′ | = k and therefore S′ is reachable by the induction hypothesis. Since S′ −→a { 0, i2, i3, . . . , ik, n − 1} = S, the set S is reachable. (ii) i1 = 0 and ik+1 < n − 1.
Take S′ = { 0, i2 + x, i3 + x, . . . , ik + x, n − 1} , where x = n − 1 − ik+1. Then | S′ | = k + 1 and S′ contains states 0 and n − 1. Therefore, the set S′ is reachable as shown in case (i). Since S′ −b→x { 0, i2, i3, . . . , ik, ik+1} = S, the set S is reachable. (iii) i1 > 0 and ik+1 < n − 1.
Take S′ = { 0, i2 − i1, i3 − i1, . . . , ik − i1, ik+1 − i1} .
Then | S′ | = k + 1 and S′ contains state 0. Therefore the set S′ is reachable as shown in cases (i) and (ii).
i Since we have | S′ | −a →1 { i1, i2, i3, . . . , ik, ik+1} = S, the set S is reachable.
We have shown that the subset automaton has 3/4.2n reachable states.
Lemma 3. All the reachable states of the subset automaton corresponding to the NFA N shown in Fig. 5 are pairwise distinguishable.
Proof. Notice that the string an−1−i is accepted by the NFA N only from the state i. By Proposition 1, no two distinct subsets of { 0, 1, . . . , n − 1} are equivalent.
Next, we need to show that { q0} and some final subset S are distinguishable. If S is a final subset, then n − 1 ∈ S. Consider the string an. The set { q0} goes on an to { 0, 1} , which is non-final set since n ≥ 3. However, the state n − 1 goes on an to n − 1 in the NFA. It follows that an is accepted by the subset automaton from S. This the string an distinguishes { q0} and S.
Hence all reachable states of the subset automaton of N are pairwise distinguishable.
As a corollary of the two lemmata above, we get the following result.
Theorem 1. Let L be the language accepted by the Maslov’s automaton shown in Fig. 4. Then the minimal DFA for the language L∗ has 3/4 · 2n states.
Proof. Let N be the NFA for the language L∗ shown in Fig. 5. By Lemma 2, the subset automaton of N has 3/4 · 2n reachable states. By Lemma 3, these states are distinguishable. It follows that the minimal DFA for L∗ has 3/4 · 2n states, which meets the upper bound given by Corollary 1.
Notice that the upper bound given by Lemma 2 depends on the number of final states in a given DFA. Now, in the main result of our paper, we present automata with k final states that meet the upper bound 2n−1 + 2n−1−k.
To this aim, consider an n-state DFA A = (Q, Σ,δ , s, F ), where •
Q = { 0, 1, . . . , n − 1} ; • Σ = { a, b} ; • s = 0; • F = { n − k, n − k + 1, n − k + 2, . . ., n − 1} ; • δ (i, a) = (i + 1) mod n, δ (0, b) = 0, δ (i, b) = i + 1 if 1 ≤ i ≤ n − 3, δ (n − 2, b) = 0, δ (n − 1, b) = n − 1.
The DFA A with k = 3 is shown in Fig. 6. Notice that
this automaton is obtained by a modification of YZS’94
automaton in Fig. 3 presented in [
Construct an NFA N for the language L(A)∗ as described in Section 3. For k = 3, the NFA N shown in Fig. 7. Consider the subset automaton of N, and let as show that this subset automaton has 2n−1 + 2n−1−k reachable and pairwise distinguishable states.
b a a,b a,b a,b a,b a,b
a 0 1 2 n−4 n−3
n−2 b b q0 a a,b
Proof. Notice that if a reachable set contains a final state of N, then it must contain also the state 0.
The set { q0} is reachable since it is the initial state of subset automaton. The set { 0} is reached from { q0} by b, and since we have { 0} −→ai { i} if 1 ≤ i ≤ n − k − 1, all We conclude this section with two observations showing subsets S with | S| = 1 are reachable. that the a numbers 1 and n can be attained by the complex
Next we have ity of Kleene closure. { n − k − 1} −→a { 0, n − k} −→b · · · −→b { 0, n − 2} , Proposition 2. For every n, there exists a binary language a bn−3 b { 0, n − 2} −→ { 0, 1, n − 1} −−→ { 0, n − 2, n − 1} −→ { 0, n − 1} , L accepted by a minimal n-state DFA such that the lana bi−1 guage L∗ has state complexity 1. { 0, n − 1} −→ { 0, 1} −−→ { 0, i} if 1 ≤ i ≤ n − k − 1.
Finally, if 1 ≤ i < j ≤ n − k − 1 then { i, j} is reached Proof. Let L = { a, b} ∪ { w | | w| ≥ n − 1} . The minimal from { 0, j − i} by ai. Thus all S with | S| = 2 are reachable. DFA for L has n states. Since a ∈ L, b ∈ L, we have L∗ =
Assume that every set S with | S| = t, where 2 ≤ t ≤ { a, b} , and therefore the state complexity of L∗ is 1. n − 1, is reachable. Let S = { i1, i2, . . . , it , it+1} , where 0 ≤ Proposition 3. For every n, there exists a binary language i1 < i2 < · · · < it < it+1 ≤ n − 1, be set of size t + 1. L accepted by a minimal n-state DFA such that the lanConsider three cases: guage L∗ has state complexity n. (i) i1 = 0 and it+1 = n − 1.
Let S′ = { 0, i3 − i2, i4 − i2, . . . , it − i2, n − 2} . Then S′ is of size t, thus it is reachable by the induction hypothesis. Since we have
bi2−1 S′ −→a { 0, 1, i3 − i2 + 1, . . . , it − i2 + 1, n − 1} −−−→ S, the set S is reachable. (ii) i1 = 0 and it+1 < n − 1.
Let S′ = { 0, i3 − i2, . . . , it+1 − i2, n − 1} . Then S′ is of size t + 1 and contains 0 and n − 1, thus S′ is reachable by (i). Since we have S′ −→a { 0, 1, i3 − i2 + 1, . . . , it − i2 + 1, it+1 − i2 + 1} bi2−1 −−−→ S, the set S is reachable. (iii) i1 > 0 and it+1 < n − k.
Take S′ = { 0, i2 − i1, i3 − i1, . . . , it − i1, it+1 − i1} .
Then | S′ | = t + 1 and S′ contains state 0. Therefore the set S′ is reachable as shown in cases (i) and (ii).
i Since we have S′ −a →1 { i1, i2, i3, . . . , it , it+1} = S, the set S is reachable.
This proves the reachability of 2n−1 + 2n−1−k states.
Lemma 5. All reachable states of the subset automaton of the NFA N are pairwise distinguishable.
Proof. Notice that in the NFA N, the string an−1−ibn is accepted only from the state i. By Proposition 1 this proves the distinguishability of subsets of { 0, 1, . . . , n − 1} . Now we need to show that { q0} is not equivalent to any final subset S of { 0, 1, . . . , n − 1} . If S is final, then there is a final state i ≥ n − k such that i ∈ S. Then an−1−ibn is accepted by the subset automaton from S and rejected from { q0} . This concludes the proof.
Now, we can state our main result.
Theorem 2. Let n ≥ 3 and 1 ≤ k ≤ n − 1. There exists an n-state DFA A with k final states such that the minimal DFA for the language L(A)∗ has 2n−1 + 2n−1−k states.
Proof. Let L = ((a + b)n)∗. The minimal DFA for L has n states. Next, we have L = L∗ and therefore the state complexity of L∗ is n. 5
In this section, we consider not only the worst case, but rather study all possible values that can be obtained as the number of states of the minimal DFA recognizing the Kleene closure of a regular language represented by a minimal n-state DFA.
For Kleene closure, the possible resulting vales are in
the range from 1 to 3/4 · 2n, and it is known that for a
growing alphabet of size 2n, no gaps in the hierarchy of
possible complexities exist [
Here we study the binary case. Using the lists of pairwise non-isomorphic minimal deterministic finite automata of 2,3,4, and 5 states, we computed the frequencies of the resulting complexities for Kleene closure, and showed that every value in the range from 1 to 3/4 · 2n occurs at least ones. 5.1
Our results for n = 2, 3, 4, 5 concerning the frequency of the resulting complexities, including the average complexity, are displayed in the four graphs shown in Figures 8-11 on the next page.
Notice that for n = 4, 5 the complexity one has the highest frequency. On the other hand, there are only a four DFA’s whose Kleene closure has complexity 2. Starting with complexity 5, the frequency has a decreasing tendency. The average values approximately n, which coresponds to the fact that the high complexities occur very rarely.
Although, in the worst case, the Kleene closure is a hard operation with an exponential complexity, its average complexity is only n, which allows the operation to be effectively used in practical applications. This subsection is different from the previous one. For n ≥ 6 we do not have input text files. We change the strategy, and consider binary automata, in which the first symbol is a circular shift of the states, and the second symbol is generated randomly. We consider an arbitrary number of final states. We run our application on such randomly generated automaton. We consider an arbitrary number of final states. We show that all values from 1 to 3/4 · 2n are attainable, and for every m with 1 ≤ m ≤ 3/4 · 2n, we provide an n-state binary DFA A such that the state complexity of L(A)∗ is exactly m. The lists of these automata for n = 6, 7, 8 follow.
Thus our computations show, that in the binary case, up to n = 8, no holes in the state complexity of Kleene closure exist. Moreover, for every n, the numbers 1, n, and 2n−1 + 2n−1−k with 1 ≤ k ≤ n − 1 are attainable by the complexity of Kleene closure. 7
We studied the complexity of languages that results from
the Kleene closure operation on regular languages. First,
we proved that the n-state automata presented by Maslov
in his 1970 paper meets the upper bound 3/4 · 2n on the
state complexity of Kleene closure. We fixed a small error
in the Maslov’s paper [
Then, in the main result of our paper, we provided the nstate binary automata with k final states, that meet the upper bound 2n−1 + 2n−1−k on the state complexity of Kleene closure.
In the second part of the paper, we considered all possible values of the complexity of Kleene closure in the binary case. Using our application and the lists of pairwise non-isomorphic minimal automata of 2,3,4, and 5 states, we computed the frequency of the resulting complexities of Kleene closure and the average complexity of Kleene closure. We showed that each possible complexity occurs at least once.
For n = 6, 7, 8, we considered automata, in which the first symbol is a circular shift of the states, the second symbol is generated randomly, and the number of final states is arbitrary. For every possible value m in the range from 1 to 3/4 · 2n, we found an n-state DFA accepted a language such that the minimal DFA for the Kleene closure of this language has exactly m states.
Thus for n ≤ 8, every value in the range from 1 to 3/4 · 2n is attainable by the complexity of the Kleene closure in the binary case. Whether this is true for larger values of n remains open. Also getting the whole range of complexities from 1 to 3/4 · 2n for any fixed alphabet, or at least for an alphabet that grows at most linearly with n, is of great interest to us.