Let be an automaton. Recall that a transition of is a triple written in the form
where is a next state of the configuration . In other words, . Here, is a symbol in .
The notion of transitions can be generalized so that iff , where . The definition of the extended transition function dictates that implies . This means that if the empty word is fed into an automaton at any state , 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 where is not necessarily . 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 concepts that need to be formalized:
An automaton with -transitions, or -automaton for short, is a sextuple
such that , and , where , is an automaton, called the automaton associated with .
An -transition is a transition of of the form .
We say that an -automaton is equivalent to an automaton if . 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)).
|Date of creation||2013-03-22 18:03:24|
|Last modified on||2013-03-22 18:03:24|
|Last modified by||CWoo (3771)|
|Synonym||automaton with epsilon-transitions|
|Defines||automaton with -transitions|