$ϵ$-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 }{⟶}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}{⟶}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 }{⟶}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 $ϵ$-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 }{⟶}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 $\lambda$, 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 concepts that need to be formalized:

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

   $$E:=(S,\mathrm{\Sigma },\delta ,I,F,ϵ)$$

   such that $ϵ\notin \mathrm{\Sigma }$, and $E_{ϵ}:=(S,{\mathrm{\Sigma }}_{ϵ},\delta ,I,F)$, where ${\mathrm{\Sigma }}_{ϵ}:=\mathrm{\Sigma }\cup \{ϵ\}$, is an automaton, called the automaton associated with $E$.

2. An $ϵ$-transition is a transition of $E_{ϵ}$ of the form $p\stackrel{ϵ}{⟶}q$.

3. We define the language $L(E)$ accepted by an $ϵ$-automaton $E$ to be the set of all words in ${\mathrm{\Sigma }}^{*}$ that can be obtained from words accepted by $E_{ϵ}$ by deleting any occurrences of $ϵ$. Formally,

   $$L(E):=h(L(E_{ϵ})),$$

   where $h:{\mathrm{\Sigma }}_{ϵ}^{*}\to {\mathrm{\Sigma }}^{*}$ is the monoid homomorphism given by $h|\mathrm{\Sigma }=1$ and $h(ϵ)=\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={ϵ}^{i_0}{\alpha }_1{ϵ}^{i_1}{\alpha }_2{ϵ}^{i_2}\mathrm{\cdots }{ϵ}^{i_{n-1}}{\alpha }_n{ϵ}^{i_n},$$

   where ${\alpha }_j\in \mathrm{\Sigma }$, $j=1,2,\mathrm{\dots },n$.

4. We say that an $ϵ$-automaton $E$ is equivalent 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 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	$ϵ$-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