# Kleene star of an automaton

Let $A=(S,\Sigma,\delta,I,F)$ be an automaton. Define the Kleene star $A^{*}$ of $A$ as an automaton with $\epsilon$-transitions (http://planetmath.org/AutomatonWithEpsilonTransitions) $(S_{1},\Sigma,\delta_{1},I_{1},F_{1},\epsilon)$ where

1. 1.

$S_{1}=S\lx@stackrel{{\scriptstyle\cdot}}{{\cup}}\{q\}$ (we either assume that $q$ is not a symbol in $\Sigma$, or we take the disjoint union)

2. 2.

$\delta_{1}$ is a function from $S_{1}\times(\Sigma\lx@stackrel{{\scriptstyle\cdot}}{{\cup}}\{\epsilon\})$ to $P(S_{1})$ given by:

• $\delta_{1}(s,\epsilon):=I$ if $s=q$, $\delta_{1}(s,\epsilon):=\{q\}$ for any $s\in F$,

• $\delta_{1}(s,\alpha):=\delta(s,\alpha)$, for any $(s,\alpha)\in S\times\Sigma$, and

• $\delta_{1}(s,\alpha):=\varnothing$ otherwise.

3. 3.

$I_{1}=F_{1}=\{q\}$

Basically, we throw into $A^{*}$ all transitions in $A$. In addition, we add to $A^{*}$ transitions taking $s$ to any initial states of $A$, as well as transitions taking any final states of $A$ to $s$. Visually, the state diagram $G_{A^{*}}$ of $A^{*}$ is obtained by adding a node $q$ to the state diagram $G_{A}$ of $A$, and making $q$ both the start and the final node of $G_{A^{*}}$. Furthermore, add edges from $q$ to the start nodes of $G_{A}$, and edges from the final nodes of $G_{A}$ to $q$, and let $\epsilon$ be the label for all of the newly added edges.

###### Proposition 1.

$L(A)^{*}=L(A^{*})$.

###### Proof.

Clearly $\lambda\in L(A)*$. In addition, since $I_{1}=F_{1}$, $\lambda\in L(A^{*}_{\epsilon})=L(A^{*})$. This proves the case when the word is empty. Now, we move to the case when the word has non-zero length.

• $L(A)^{*}\subseteq L(A^{*})$.

Suppose $a=a_{1}a_{2}\cdots a_{n}$ is a word such that $a_{i}\in L(A)$, then we claim that $b=b_{1}b_{2}\cdots b_{n}$, where $b_{i}=\epsilon a_{i}\epsilon$, is accepted by $A^{*}_{\epsilon}$. This can be proved by induction on $n$:

1. (a)

First, $n=1$. Then

 $\delta_{1}(q,b_{1})=\delta_{1}(\delta_{1}(q,\epsilon),a_{1}\epsilon)=\delta_{1% }(I,a_{1}\epsilon)=\delta_{1}(\delta_{1}(I,a_{1}),\epsilon).$

Since $a_{1}$ is accepted by $A$, $\delta_{1}(I,a_{1})=\delta(I,a_{1})$ contains an accepting state $s\in F$, so that

 $q\in\delta_{1}(s,\epsilon)\subseteq\delta_{1}(\delta_{1}(I,a_{1}),\epsilon).$

Hence $b_{1}$ is accepted by $A^{*}_{\epsilon}$.

2. (b)

Next, suppose that given $b=b_{1}\cdots b_{n}$, the subword $b_{1}\cdots b_{n-1}$ (induction step) is accepted by $A^{*}_{\epsilon}$. This means that $q\in\delta_{1}(q,b_{1}\cdots b_{n-1})$, so that

 $\delta_{1}(q,b_{n})\subseteq\delta_{1}(\delta_{1}(q,b_{1}\cdots b_{n-1}),b_{n}% )=\delta_{1}(q,b_{1}\cdots b_{n}).$

But $\delta_{1}(q,b_{n})$ contains $q$ as was shown in step 1 above. As a result, $b_{1}\cdots b_{n}$ is accepted by $A^{*}_{\epsilon}$.

This shows that $L(A)^{*}\subseteq L(A^{*})$.

• $L(A^{*})\subseteq L(A)^{*}$.

Suppose now that $a$ is a word over $\Sigma$ accepted by $A^{*}$. This means that, for some $i_{j}$, $j=0,1,\ldots,n$, the word

 $b:=\epsilon^{i_{0}}a_{1}\epsilon^{i_{1}}\cdots\epsilon^{i_{n-1}}a_{n}\epsilon^% {i_{n}}$

is accepted by $A^{*}_{\epsilon}$, where each $a_{j}$ is a word over $\Sigma$ with $a=a_{1}\cdots a_{n}$. We want to show that each $a_{j}$ is accepted by $A$.

The main thing is to notice is that if $q\in\delta_{1}(J,\epsilon^{i})$ and $J\subseteq S$, where $i$ is a positive integer, then $J$ must contain a state in $F$. Otherwise, $J\subseteq S-F$, so that $\delta_{1}(J,\epsilon)=\varnothing$, and we must have $\delta_{1}(J,\epsilon^{i})=\delta_{1}(\delta_{1}(J,\epsilon),\epsilon^{i-1})=% \delta_{1}(\varnothing,\epsilon^{i-1})=\varnothing$.

Set $J=\delta_{1}(q,\epsilon^{i_{0}}a_{1}\epsilon^{i_{1}}\cdots\epsilon^{i_{n-1}}a_% {n})$ and $K=\delta_{1}(q,\epsilon^{i_{0}}a_{1}\epsilon^{i_{1}}\cdots\epsilon^{i_{n-1}})$. Then $J=\delta_{1}(K,a_{n})=\delta(K,a_{n})\subseteq S$. Furthermore, by assumption $q\in\delta_{1}(q,b)=\delta_{1}(J,\epsilon^{i_{n}})$. Therefore, $J$ must contain a state in $F$. Thus, $a_{n}$ is accepted by $A$. The fact that the remaining $a_{i}$’s are accepted by $A$ is proved inductively.

This shows that $L(A^{*})\subseteq L(A)^{*}$.

This completes the proof. ∎

Title Kleene star of an automaton KleeneStarOfAnAutomaton 2013-03-22 18:04:06 2013-03-22 18:04:06 CWoo (3771) CWoo (3771) 16 CWoo (3771) Definition msc 03D05 msc 68Q45