$\u03f5$transition
Let $A=(S,\mathrm{\Sigma},\delta ,I,F)$ be an automaton. Recall that a transition of $A$ is a triple written in the form
$$p\stackrel{\alpha}{\u27f6}q,$$ 
where $q$ is a next state of the configuration^{} $(p,\alpha )$. In other words, $q\in \delta (p,\alpha )$. Here, $\alpha $ is a symbol in $\mathrm{\Sigma}$.
The notion of transitions can be generalized so that $p\stackrel{a}{\u27f6}q$ iff $q\in \delta (p,a)$, where $a\in {\mathrm{\Sigma}}^{*}$. The definition of the extended transition function $\delta $ dictates that $p\stackrel{\lambda}{\u27f6}q$ implies $p=q$. This means that if the empty word^{} is fed into an automaton at any state $p$, the next state stays the same. In other words, the automaton does nothing.
An $\u03f5$transition, informally, is a transition in an “automaton” that changes the initial state when an empty word is read. This means, notationally, that $p\stackrel{\lambda}{\u27f6}q$ where $p$ is not necessarily $q$. The double quotes around the word automaton is to signify the fact that when $\u03f5$transitions are considered, the machine is no longer an automaton strictly speaking. The “$\u03f5$” here refers to the empty word $\lambda $, which is sometimes denoted by $\u03f5$.
The consequence of adding $\u03f5$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 $\u03f5$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 $\u03f5$transitions and automata with $\u03f5$transitions are.
Definitions. There are several concepts^{} that need to be formalized:

1.
An automaton with $\u03f5$transitions, or $\u03f5$automaton for short, is a sextuple
$$E:=(S,\mathrm{\Sigma},\delta ,I,F,\u03f5)$$ such that $\u03f5\notin \mathrm{\Sigma}$, and ${E}_{\u03f5}:=(S,{\mathrm{\Sigma}}_{\u03f5},\delta ,I,F)$, where ${\mathrm{\Sigma}}_{\u03f5}:=\mathrm{\Sigma}\cup \{\u03f5\}$, is an automaton, called the automaton associated with $E$.

2.
An $\u03f5$transition is a transition of ${E}_{\u03f5}$ of the form $p\stackrel{\u03f5}{\u27f6}q$.

3.
We define the language^{} $L(E)$ accepted by an $\u03f5$automaton $E$ to be the set of all words in ${\mathrm{\Sigma}}^{*}$ that can be obtained from words accepted by ${E}_{\u03f5}$ by deleting any occurrences of $\u03f5$. Formally,
$$L(E):=h(L({E}_{\u03f5})),$$ where $h:{\mathrm{\Sigma}}_{\u03f5}^{*}\to {\mathrm{\Sigma}}^{*}$ is the monoid homomorphism given by $h\mathrm{\Sigma}=1$ and $h(\u03f5)=\lambda $. It is easy to see, by induction^{}, that
$$h(a)={\alpha}_{1}{\alpha}_{2}\mathrm{\cdots}{\alpha}_{n}\mathit{\hspace{1em}\hspace{1em}}\text{iff}\mathit{\hspace{1em}\hspace{1em}}a={\u03f5}^{{i}_{0}}{\alpha}_{1}{\u03f5}^{{i}_{1}}{\alpha}_{2}{\u03f5}^{{i}_{2}}\mathrm{\cdots}{\u03f5}^{{i}_{n1}}{\alpha}_{n}{\u03f5}^{{i}_{n}},$$ where ${\alpha}_{j}\in \mathrm{\Sigma}$, $j=1,2,\mathrm{\dots},n$.

4.
We say that an $\u03f5$automaton $E$ is equivalent^{} to an automaton $A$ if $L(E)=L(A)$. It is not hard to see that every $\u03f5$automaton is equivalent to an automaton (proof here (http://planetmath.org/EveryEpsilonAutomatonIsEquivalentToAnAutomaton)).
Remark. $\u03f5$transitions are useful in proving the two properties of regular languages: 1. if two languages are regular^{}, 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  $\u03f5$transition 

Canonical name  epsilontransition 
Date of creation  20130322 18:03:24 
Last modified on  20130322 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  $\u03f5$automaton 
Synonym  epsilonautomaton 
Synonym  epsilontransition 
Synonym  automaton with epsilontransitions 
Defines  automaton with $\u03f5$transitions 