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

1.
${S}_{1}=S\stackrel{\cdot}{\cup}\{q\}$ (we either assume that $q$ is not a symbol in $\mathrm{\Sigma}$, or we take the disjoint union^{})

2.
${\delta}_{1}$ is a function from ${S}_{1}\times (\mathrm{\Sigma}\stackrel{\cdot}{\cup}\{\u03f5\})$ to $P({S}_{1})$ given by:

–
${\delta}_{1}(s,\u03f5):=I$ if $s=q$, ${\delta}_{1}(s,\u03f5):=\{q\}$ for any $s\in F$,

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

–
${\delta}_{1}(s,\alpha ):=\mathrm{\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 $\u03f5$ 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}_{\u03f5}^{*})=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}\mathrm{\cdots}{a}_{n}$ is a word such that ${a}_{i}\in L(A)$, then we claim that $b={b}_{1}{b}_{2}\mathrm{\cdots}{b}_{n}$, where ${b}_{i}=\u03f5{a}_{i}\u03f5$, is accepted by ${A}_{\u03f5}^{*}$. This can be proved by induction^{} on $n$:

(a)
First, $n=1$. Then
$${\delta}_{1}(q,{b}_{1})={\delta}_{1}({\delta}_{1}(q,\u03f5),{a}_{1}\u03f5)={\delta}_{1}(I,{a}_{1}\u03f5)={\delta}_{1}({\delta}_{1}(I,{a}_{1}),\u03f5).$$ 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,\u03f5)\subseteq {\delta}_{1}({\delta}_{1}(I,{a}_{1}),\u03f5).$$ Hence ${b}_{1}$ is accepted by ${A}_{\u03f5}^{*}$.

(b)
Next, suppose that given $b={b}_{1}\mathrm{\cdots}{b}_{n}$, the subword ${b}_{1}\mathrm{\cdots}{b}_{n1}$ (induction step) is accepted by ${A}_{\u03f5}^{*}$. This means that $q\in {\delta}_{1}(q,{b}_{1}\mathrm{\cdots}{b}_{n1})$, so that
$${\delta}_{1}(q,{b}_{n})\subseteq {\delta}_{1}({\delta}_{1}(q,{b}_{1}\mathrm{\cdots}{b}_{n1}),{b}_{n})={\delta}_{1}(q,{b}_{1}\mathrm{\cdots}{b}_{n}).$$ But ${\delta}_{1}(q,{b}_{n})$ contains $q$ as was shown in step 1 above. As a result, ${b}_{1}\mathrm{\cdots}{b}_{n}$ is accepted by ${A}_{\u03f5}^{*}$.
This shows that $L{(A)}^{*}\subseteq L({A}^{*})$.

(a)

•
$L({A}^{*})\subseteq L{(A)}^{*}$.
Suppose now that $a$ is a word over $\mathrm{\Sigma}$ accepted by ${A}^{*}$. This means that, for some ${i}_{j}$, $j=0,1,\mathrm{\dots},n$, the word
$$b:={\u03f5}^{{i}_{0}}{a}_{1}{\u03f5}^{{i}_{1}}\mathrm{\cdots}{\u03f5}^{{i}_{n1}}{a}_{n}{\u03f5}^{{i}_{n}}$$ is accepted by ${A}_{\u03f5}^{*}$, where each ${a}_{j}$ is a word over $\mathrm{\Sigma}$ with $a={a}_{1}\mathrm{\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,{\u03f5}^{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,\u03f5)=\mathrm{\varnothing}$, and we must have ${\delta}_{1}(J,{\u03f5}^{i})={\delta}_{1}({\delta}_{1}(J,\u03f5),{\u03f5}^{i1})={\delta}_{1}(\mathrm{\varnothing},{\u03f5}^{i1})=\mathrm{\varnothing}$.
Set $J={\delta}_{1}(q,{\u03f5}^{{i}_{0}}{a}_{1}{\u03f5}^{{i}_{1}}\mathrm{\cdots}{\u03f5}^{{i}_{n1}}{a}_{n})$ and $K={\delta}_{1}(q,{\u03f5}^{{i}_{0}}{a}_{1}{\u03f5}^{{i}_{1}}\mathrm{\cdots}{\u03f5}^{{i}_{n1}})$. 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,{\u03f5}^{{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 

Canonical name  KleeneStarOfAnAutomaton 
Date of creation  20130322 18:04:06 
Last modified on  20130322 18:04:06 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  16 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03D05 
Classification  msc 68Q45 