every $ϵ$-automaton is equivalent to an automaton

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

Proposition 1.

Every $ϵ$-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,\mathrm{\Sigma },\delta ,I,F,ϵ)$ is an $ϵ$-automaton, and $E_{ϵ}$ is the automaton associated with $E$,

• $h:{(\mathrm{\Sigma }\cup \{ϵ\})}^{*}\to {\mathrm{\Sigma }}^{*}$ is the homomorphism that erases $ϵ$ (it takes $ϵ$ to the empty word, also denoted by $ϵ$). From the parent entry, $L(E):=h(L(E_{ϵ}))$.

Proof.

Define a function ${\delta }_1:S\times \mathrm{\Sigma }\to P(S)$, as follows: for each pair $(s,a)\in S\times \mathrm{\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 ${ϵ}^{m}a{ϵ}^n$. As usual, we extend ${\delta }_1$ so its domain is $S\times {\mathrm{\Sigma }}^{*}$. By abuse of notation, we use ${\delta }_1$ again for this extension. First, we set ${\delta }_1(s,ϵ):=\{s\}$. Then we inductively define ${\delta }_1(s,ua)={\delta }_1({\delta }_1(s,u),a)$. Using induction,

${\delta }_1(s,ua)$$=$${\delta }_1({\delta }_1(s,u),a)$

$=$${\delta }_1({\displaystyle \bigcup _{h(v)=u}}\delta (s,v),a)$

$=$${\displaystyle \bigcup _{h(v)=u}}{\delta }_1(\delta (s,v),a)$

$=$${\displaystyle \bigcup _{h(v)=u}}{\displaystyle \bigcup _{t\in \delta (s,v)}}{\delta }_1(t,a)$

$=$${\displaystyle \bigcup _{h(v)=u}}{\displaystyle \bigcup _{t\in \delta (s,v)}}{\displaystyle \bigcup _{h(w)=a}}\delta (t,w)$

$=$${\displaystyle \bigcup _{h(v)=u}}{\displaystyle \bigcup _{h(w)=a}}{\displaystyle \bigcup _{t\in \delta (s,v)}}\delta (t,w)$

$=$${\displaystyle \bigcup _{h(v)=u}}{\displaystyle \bigcup _{h(w)=a}}\delta (\delta (s,v),w)$

$=$${\displaystyle \bigcup _{h(v)=u}}{\displaystyle \bigcup _{h(w)=a}}\delta (s,vw)$

$=$${\displaystyle \bigcup \{\delta (s,vw)\mid h(v)=u\text{ and }h(w)=a\}}$

$=$${\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\mathrm{\cdots }{a}_n$, then ${\delta }_1(s,u)$ is the set of all states reachable from $s$ by words of the form

$${ϵ}^{i_0}{a}_1{ϵ}^{i_1}{a}_2{ϵ}^{i_2}\mathrm{\cdots }{ϵ}^{i_{n-1}}{a}_n{ϵ}^{i_n}.$$(2)

Now, define $A$ to be the automaton $(S,\mathrm{\Sigma },{\delta }_1,I,F)$. Then, from equation (1) above, a word

$$u=a_1{a}_2\mathrm{\cdots }{a}_n$$

is accepted by $A$ iff some word $v$ of the form (2) is accepted by $E_{ϵ}$ iff $u=h(v)$ is accepted by $E$, proving the proposition.∎

Remark. Another approach is to use the concept of $ϵ$-closure (http://planetmath.org/EpsilonClosure). The proof is very similar to the one given above, and the resulting equivalent automaton is a DFA.