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.
Every -automaton (http://planetmath.org/EpsilonAutomaton) is equivalent to an automaton.
For the proof, we use the following setup (see the parent entry for more detail):
is an -automaton, and is the automaton associated with ,
Define a function , as follows: for each pair , let
In other words, is the set of all states reachable from by words of the form . As usual, we extend so its domain is . By abuse of notation, we use again for this extension. First, we set . Then we inductively define . Using induction,
So for any non-empty word , we have the following equation:
In other words, if , then is the set of all states reachable from by words of the form
Now, define to be the automaton . Then, from equation (1) above, a word
is accepted by iff some word of the form (2) is accepted by iff is accepted by , proving the proposition. ∎
|Title||every -automaton is equivalent to an automaton|
|Date of creation||2013-03-22 19:02:03|
|Last modified on||2013-03-22 19:02:03|
|Last modified by||CWoo (3771)|