Let A=(S,Σ,δ,I,F) be an automaton. Recall that a transition of A is a triple written in the form


where q is a next state of the configurationMathworldPlanetmath (p,α). In other words, qδ(p,α). Here, α is a symbol in Σ.

The notion of transitions can be generalized so that paq iff qδ(p,a), where aΣ*. The definition of the extended transition function δ dictates that pλq implies p=q. This means that if the empty wordPlanetmathPlanetmathPlanetmath is fed into an automaton at any state p, the next state stays the same. In other words, the automaton does nothing.

An ϵ-transition, informally, is a transition in an “automaton” that changes the initial state when an empty word is read. This means, notationally, that pλq where p is not necessarily q. The double quotes around the word automaton is to signify the fact that when ϵ-transitions are considered, the machine is no longer an automaton strictly speaking. The “ϵ” here refers to the empty word λ, which is sometimes denoted by ϵ.

The consequence of adding ϵ-transitions is that the set of next states is potentially enlarged whenever a word is read, because at any point during the reading, a next state could result from an alphabet, or it could come from any of the next states by inserting several empty words after the alphabet. Outwardly, the insertions of empty words into a word does not change the word itself. However, the possibility of accepting the word is increased. So the question is: does this “automaton with ϵ-transitoins” offers more computing power than a traditional automaton? Interestingly, the answer is no, and we will demonstrate this fact in this article.

First, we need to define formally what ϵ-transitions and automata with ϵ-transitions are.

Definitions. There are several conceptsMathworldPlanetmath that need to be formalized:

  1. 1.

    An automaton with ϵ-transitions, or ϵ-automaton for short, is a sextuple


    such that ϵΣ, and Eϵ:=(S,Σϵ,δ,I,F), where Σϵ:=Σ{ϵ}, is an automaton, called the automaton associated with E.

  2. 2.

    An ϵ-transition is a transition of Eϵ of the form pϵq.

  3. 3.

    We define the languagePlanetmathPlanetmath L(E) accepted by an ϵ-automaton E to be the set of all words in Σ* that can be obtained from words accepted by Eϵ by deleting any occurrences of ϵ. Formally,


    where h:Σϵ*Σ* is the monoid homomorphism given by h|Σ=1 and h(ϵ)=λ. It is easy to see, by inductionMathworldPlanetmath, that

    h(a)=α1α2αn   iff   a=ϵi0α1ϵi1α2ϵi2ϵin-1αnϵin,

    where αjΣ, j=1,2,,n.

  4. 4.

    We say that an ϵ-automaton E is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to an automaton A if L(E)=L(A). It is not hard to see that every ϵ-automaton is equivalent to an automaton (proof here (http://planetmath.org/EveryEpsilonAutomatonIsEquivalentToAnAutomaton)).

Remark. ϵ-transitions are useful in proving the two properties of regular languages: 1. if two languages are regularPlanetmathPlanetmathPlanetmath, so is their juxtaposition (see proof here (http://planetmath.org/JuxtapositionOfAutomata)), and 2. if a language is regular, so is its Kleene star (see proof here (http://planetmath.org/KleeneStarOfAnAutomaton)).

Title ϵ-transition
Canonical name epsilontransition
Date of creation 2013-03-22 18:03:24
Last modified on 2013-03-22 18:03:24
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 20
Author CWoo (3771)
Entry type Definition
Classification msc 03D05
Classification msc 68Q45
Synonym ϵ-automaton
Synonym epsilon-automaton
Synonym epsilon-transition
Synonym automaton with epsilon-transitions
Defines automaton with ϵ-transitions