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 $ϵ$-transitions (http://planetmath.org/AutomatonWithEpsilonTransitions) $(S_1,\mathrm{\Sigma },{\delta }_1,I_1,F_1,ϵ)$ 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 }\{ϵ\})$ to $P(S_1)$ given by:

   • ${\delta }_1(s,ϵ):=I$ if $s=q$, ${\delta }_1(s,ϵ):=\{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 $ϵ$ 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_{ϵ}^{*})=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\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=ϵa_iϵ$, is accepted by $A_{ϵ}^{*}$. This can be proved by induction on $n$:

  1. First, $n=1$. Then

     $${\delta }_1(q,b_1)={\delta }_1({\delta }_1(q,ϵ),a_1ϵ)={\delta }_1(I,a_1ϵ)={\delta }_1({\delta }_1(I,a_1),ϵ).$$

     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,ϵ)\subseteq {\delta }_1({\delta }_1(I,a_1),ϵ).$$

     Hence $b_1$ is accepted by $A_{ϵ}^{*}$.

  2. Next, suppose that given $b=b_1\mathrm{\cdots }{b}_n$, the subword $b_1\mathrm{\cdots }{b}_{n-1}$ (induction step) is accepted by $A_{ϵ}^{*}$. This means that $q\in {\delta }_1(q,b_1\mathrm{\cdots }{b}_{n-1})$, so that

     $${\delta }_1(q,b_n)\subseteq {\delta }_1({\delta }_1(q,b_1\mathrm{\cdots }{b}_{n-1}),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_{ϵ}^{*}$.

  This shows that $L{(A)}^{*}\subseteq L(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:={ϵ}^{i_0}{a}_1{ϵ}^{i_1}\mathrm{\cdots }{ϵ}^{i_{n-1}}{a}_n{ϵ}^{i_n}$$

  is accepted by $A_{ϵ}^{*}$, 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,{ϵ}^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,ϵ)=\mathrm{\varnothing }$, and we must have ${\delta }_1(J,{ϵ}^i)={\delta }_1({\delta }_1(J,ϵ),{ϵ}^{i-1})={\delta }_1(\mathrm{\varnothing },{ϵ}^{i-1})=\mathrm{\varnothing }$.

  Set $J={\delta }_1(q,{ϵ}^{i_0}{a}_1{ϵ}^{i_1}\mathrm{\cdots }{ϵ}^{i_{n-1}}{a}_n)$ and $K={\delta }_1(q,{ϵ}^{i_0}{a}_1{ϵ}^{i_1}\mathrm{\cdots }{ϵ}^{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,{ϵ}^{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	2013-03-22 18:04:06
Last modified on	2013-03-22 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