# every $\epsilon$-automaton is equivalent to an automaton

In this entry, we show that an automaton with $\epsilon$-transitions (http://planetmath.org/EpsilonTransition) is no more power than one without. Having $\epsilon$-transitions is purely a matter of convenience.

###### Proposition 1.

Every $\epsilon$-automaton (http://planetmath.org/EpsilonAutomaton) 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 non-empty 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_{n% -1}}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 (http://planetmath.org/EpsilonClosure). The proof is very similar to the one given above, and the resulting equivalent automaton is a DFA.

Title every $\epsilon$-automaton is equivalent to an automaton EveryepsilonautomatonIsEquivalentToAnAutomaton 2013-03-22 19:02:03 2013-03-22 19:02:03 CWoo (3771) CWoo (3771) 8 CWoo (3771) Definition msc 03D05 msc 68Q45