You are here
HomeKleene star of an automaton
Primary tabs
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 $(S_{1},\Sigma,\delta_{1},I_{1},F_{1},\epsilon)$ where
1. $S_{1}=S\stackrel{\cdot}{\cup}\{q\}$ (we either assume that $q$ is not a symbol in $\Sigma$, or we take the disjoint union)
2. $\delta_{1}$ is a function from $S_{1}\times(\Sigma\stackrel{\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. $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 nonzero 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$:
(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}}$.
(b) Next, suppose that given $b=b_{1}\cdots b_{n}$, the subword $b_{1}\cdots b_{{n1}}$ (induction step) is accepted by $A^{*}_{{\epsilon}}$. This means that $q\in\delta_{1}(q,b_{1}\cdots b_{{n1}})$, so that
$\delta_{1}(q,b_{n})\subseteq\delta_{1}(\delta_{1}(q,b_{1}\cdots b_{{n1}}),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_{{n1}}}}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 SF$, so that $\delta_{1}(J,\epsilon)=\varnothing$, and we must have $\delta_{1}(J,\epsilon^{i})=\delta_{1}(\delta_{1}(J,\epsilon),\epsilon^{{i1}})% =\delta_{1}(\varnothing,\epsilon^{{i1}})=\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. ∎
Mathematics Subject Classification
03D05 no label found68Q45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections