Finite state machine with epsilon transitions
Finite state machine with epsilon transitions is an extension of a finite state machine where transitions can be labelled by . If such a transition exists then an automaton may transition from to without consuming any portion of the input string.
As for finite state machine, we define a finite state machine with epsilon transitions as a 5-tuple with the only difference that where is a special symbol.
Execution of machine with epsilon transitions
An execution is now an alternating sequence of states and elements of . As before, an accepting execution starts from initial state and its last item is a final state. The word accepted by a given accepting execution is given by concatenating the labels of all transitions in an execution, with transitions ignored.
Note: we could further generalize to allow arbitrary strings
Eliminating epsilon transitions
Epsilon transitions are a matter of convenience and can always be eliminated by the following process. For each state we compute the set of all states reachable from along the edges with transitions. We then add the outgoing non-epsilon edges of all such to the existing outgoing edges of . We also insert into whenever one of the states is in . The resulting automaton accepts the same langauge and has no transitions.