Regular language closure
Kapitoly: Closure of regular languages, Unification, Access, The Difference, Supplement, Concatenation, Conclusion
We have a regular language L. We prove that the closure of L is again a regular language.
What is a language closure
We denote the closure of the language L as $L^\ast$. The closure contains all the words that can be put together by concatenating a finite number of words from the language L. We can define a closure as:
$$ L^\ast = \left\{a_1\circ a_2 \circ \dots \circ a_n ,|, a_i \in L, n \in \mathbb{N}_0 \right\}, $$
where $\circ$ denotes the concatenation operation. A closure also contains an empty word, i.e. ε.
Formal procedure
We will proceed in a very similar way as in the case of language concatenation. Only instead of linking two different automata, we link one automaton - thus leading epsilon transitions from the end states of the automaton to the initial state of the automaton. However, the closure must also contain an empty word. How to arrange it? We can make the initial state the end state. Then such an automaton would accept the empty word, but it could also accept some other word. Therefore, instead, we create a new initial state and from this new initial state we lead the epsilon transition to the original initial state.
We have a regular language L1 and an automaton that accepts this language:
\begin{eqnarray} A_1&=&\left<Q_1, \Sigma_1, \delta_1, q_0, F_1\right> \end{eqnarray}
We construct a non-deterministic automaton $A=\left<Q, \Sigma, \delta, q_s, F\right>$, for which the following holds:
- Q = Q1 ∪ {qs}
- $\Sigma = \Sigma_1$
- F = F1 ∪ {qs}
We define the transition function δ as follows:
$$ \delta(q, a) = \begin{cases} \delta_1(q, a)&\mbox{ If }&q\in Q_1 \wedge q\notin F_1\\ \delta_1(q, a)&\mbox{ If }&q\in F_1 \wedge a\ne \epsilon\\ \delta_1(q, a)\cup\left\{q_0\right\}&\mbox{ If }&q\in F_1 \wedge a= \epsilon\\ \left\{q_0\right\}&\mbox{ If }&q=q_s \wedge a= \epsilon\\ \emptyset&\mbox{ If }&q=q_s \wedge a\ne \epsilon\\ \end{cases} $$
Example
Consider this automaton A1, which accepts the words 00 or 11:
The closure of the language L(A1) is thus the language of all words that consist of pairs 00 and 11, for example 0000, 110011, 11110000, etc. We would construct an automaton that accepts this closure by creating a new initial state qs with an epsilon transition to the former initial state q0 and adding epsilon transitions from the states q3 and q4 to the state q0:
We can verify that this automaton does indeed accept the words 0000, 110011, 11110000, but will not accept, say, 1010.