You are here
Homeevery $\epsilon$automaton is equivalent to an automaton
Primary tabs
every $\epsilon$automaton is equivalent to an automaton
In this entry, we show that an automaton with $\epsilon$transitions is no more power than one without. Having $\epsilon$transitions is purely a matter of convenience.
Proposition 1.
Every $\epsilon$automaton is equivalent to an automaton.
For the proof, we use the following setup (see the parent entry for more detail):

$E=(S,\Sigma,\delta,I,F,\epsilon)$ is an $\epsilon$automaton, and $E_{{\epsilon}}$ is the automaton associated with $E$,

$h:(\Sigma\cup\{\epsilon\})^{*}\to\Sigma^{*}$ is the homomorphism that erases $\epsilon$ (it takes $\epsilon$ to the empty word, also denoted by $\epsilon$). From the parent entry, $L(E):=h(L(E_{{\epsilon}}))$.
Proof.
Define a function $\delta_{1}:S\times\Sigma\to P(S)$, as follows: for each pair $(s,a)\in S\times\Sigma$, let
$\delta_{1}(s,a)=\bigcup\,\{\,\delta(s,u)\mid h(u)=a\,\}.$ 
In other words, $\delta_{1}(s,a)$ is the set of all states reachable from $s$ by words of the form $\epsilon^{m}a\epsilon^{n}$. As usual, we extend $\delta_{1}$ so its domain is $S\times\Sigma^{*}$. By abuse of notation, we use $\delta_{1}$ again for this extension. First, we set $\delta_{1}(s,\epsilon):=\{s\}$. Then we inductively define $\delta_{1}(s,ua)=\delta_{1}(\delta_{1}(s,u),a)$. Using induction,
$\displaystyle\delta_{1}(s,ua)$  $\displaystyle=$  $\displaystyle\delta_{1}(\delta_{1}(s,u),a)$  
$\displaystyle=$  $\displaystyle\delta_{1}(\bigcup_{{h(v)=u}}\delta(s,v),a)$  
$\displaystyle=$  $\displaystyle\bigcup_{{h(v)=u}}\delta_{1}(\delta(s,v),a)$  
$\displaystyle=$  $\displaystyle\bigcup_{{h(v)=u}}\;\bigcup_{{t\in\delta(s,v)}}\delta_{1}(t,a)$  
$\displaystyle=$  $\displaystyle\bigcup_{{h(v)=u}}\;\bigcup_{{t\in\delta(s,v)}}\;\bigcup_{{h(w)=a% }}\delta(t,w)$  
$\displaystyle=$  $\displaystyle\bigcup_{{h(v)=u}}\;\bigcup_{{h(w)=a}}\;\bigcup_{{t\in\delta(s,v)% }}\delta(t,w)$  
$\displaystyle=$  $\displaystyle\bigcup_{{h(v)=u}}\;\bigcup_{{h(w)=a}}\delta(\delta(s,v),w)$  
$\displaystyle=$  $\displaystyle\bigcup_{{h(v)=u}}\;\bigcup_{{h(w)=a}}\delta(s,vw)$  
$\displaystyle=$  $\displaystyle\bigcup\{\delta(s,vw)\mid h(v)=u\mbox{ and }h(w)=a\}$  
$\displaystyle=$  $\displaystyle\bigcup\{\delta(s,x)\mid h(x)=ua\}$ 
So for any nonempty word $u$, we have the following equation:
$\delta_{1}(s,u)=\bigcup\,\{\,\delta(s,v)\mid h(v)=u\,\}.$  (1) 
In other words, if $u=a_{1}a_{2}\cdots a_{n}$, then $\delta_{1}(s,u)$ is the set of all states reachable from $s$ by words of the form
$\epsilon^{{i_{0}}}a_{1}\epsilon^{{i_{1}}}a_{2}\epsilon^{{i_{2}}}\cdots\epsilon% ^{{i_{{n1}}}}a_{n}\epsilon^{{i_{n}}}.$  (2) 
Now, define $A$ to be the automaton $(S,\Sigma,\delta_{1},I,F)$. Then, from equation (1) above, a word
$u=a_{1}a_{2}\cdots a_{n}$ 
is accepted by $A$ iff some word $v$ of the form (2) is accepted by $E_{{\epsilon}}$ iff $u=h(v)$ is accepted by $E$, proving the proposition. ∎
Remark. Another approach is to use the concept of $\epsilon$closure. The proof is very similar to the one given above, and the resulting equivalent automaton is a DFA.
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