Kleene closure of a regular language

Let L be a regular language. We will prove that the Kleene closure of the language L is again a regular language.

What the closure of a language is

We write the Kleene closure of a language L as L^∗. The closure contains all the strings that can be built by concatenating a finite number of strings from the language L. We can define the closure as:

$$L^{\ast }=\{a_1\circ a_2\circ \cdots \circ a_n|a_i\in L,n\in {\mathbb{N}}_0\},$$

where ∘ denotes the operation of concatenation. The closure also contains the empty string, that is, ϵ.

Formal construction

We proceed in a very similar way to the case of the concatenation of languages. Instead of joining two different automata, we join one automaton to itself – from the accepting states of the automaton we add epsilon transitions to its start state. However, the closure must also contain the empty string. How can we arrange that? We could make the start state an accepting state. Then the automaton would accept the empty string, but it might also accept some other strings. So instead we create a new start state and add an epsilon transition from this new start state to the original start state.

Let L₁ be a regular language and let this automaton accept it:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\end{array}$$

We construct a non-deterministic automaton A = ⟨Q, Σ, δ, q_s, F⟩ for which the following holds:

• Q = Q₁ ∪ {q_s}
• Σ= Σ₁
• F = F₁ ∪ {q_s}

We define the transition function δ as follows:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{if}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{if}& q\in F_1\wedge a\ne ϵ\\ {\delta }_1(q,a)\cup \left\{q_0\right\}& \text{if}& q\in F_1\wedge a=ϵ\\ \left\{q_0\right\}& \text{if}& q=q_s\wedge a=ϵ\\ \mathrm{\varnothing }& \text{if}& q=q_s\wedge a\ne ϵ\end{array}$$

Example

Let A₁ be this automaton, which accepts the strings 00 or 11:

The closure of the language L(A₁) is therefore the language of all strings made up of pairs 00 and 11, for example 0000, 110011, 11110000 and so on. We would build an automaton accepting this closure by creating a new start state q_s with an epsilon transition to the former start state q₀, and by adding epsilon transitions from the states q₃ and q₄ to the state q₀:

We can check that this automaton really does accept the strings 0000, 110011 and 11110000, but does not accept, for instance, the string 1010.

Sources

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools