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 equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to an automaton.

For the proof, we use the following setup (see the parent entry for more detail):

  • E=(S,Σ,δ,I,F,ϵ) is an ϵ-automaton, and Eϵ is the automaton associated with E,

  • h:(Σ{ϵ})*Σ* is the homomorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath that erases ϵ (it takes ϵ to the empty wordPlanetmathPlanetmathPlanetmath, also denoted by ϵ). From the parent entry, L(E):=h(L(Eϵ)).


Define a function δ1:S×ΣP(S), as follows: for each pair (s,a)S×Σ, let


In other words, δ1(s,a) is the set of all states reachablePlanetmathPlanetmath from s by words of the form ϵmaϵn. As usual, we extend δ1 so its domain is S×Σ*. By abuse of notation, we use δ1 again for this extensionPlanetmathPlanetmathPlanetmath. First, we set δ1(s,ϵ):={s}. Then we inductively define δ1(s,ua)=δ1(δ1(s,u),a). Using inductionMathworldPlanetmath,

δ1(s,ua) = δ1(δ1(s,u),a)
= δ1(h(v)=uδ(s,v),a)
= h(v)=uδ1(δ(s,v),a)
= h(v)=utδ(s,v)δ1(t,a)
= h(v)=utδ(s,v)h(w)=aδ(t,w)
= h(v)=uh(w)=atδ(s,v)δ(t,w)
= h(v)=uh(w)=aδ(δ(s,v),w)
= h(v)=uh(w)=aδ(s,vw)
= {δ(s,vw)h(v)=u and h(w)=a}
= {δ(s,x)h(x)=ua}

So for any non-empty word u, we have the following equation:

δ1(s,u)={δ(s,v)h(v)=u}. (1)

In other words, if u=a1a2an, then δ1(s,u) is the set of all states reachable from s by words of the form

ϵi0a1ϵi1a2ϵi2ϵin-1anϵin. (2)

Now, define A to be the automaton (S,Σ,δ1,I,F). Then, from equation (1) above, a word


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 propositionPlanetmathPlanetmath. ∎

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

Title every ϵ-automaton is equivalent to an automaton
Canonical name EveryepsilonautomatonIsEquivalentToAnAutomaton
Date of creation 2013-03-22 19:02:03
Last modified on 2013-03-22 19:02:03
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 8
Author CWoo (3771)
Entry type Definition
Classification msc 03D05
Classification msc 68Q45