This is an old revision of the document!

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 $\epsilon$ . If such a transition $(q_1,\epsilon,q_2)$ exists then an automaton may transition from $q_1$ to $q_2$ 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 $A = (\Sigma,Q,\Delta,q_0,F)$ with the only difference that $\Delta \subseteq Q \times (\Sigma \cup \{\epsilon\}) \times Q$ where $\epsilon \notin \Sigma$ is a special symbol.

An execution is now an alternating sequence of states and elements of $\Sigma \cup \{\epsilon\}$ . The word accepted by a given accepting execution is given by concatenating the labels of all transitions in an execution, with $\epsilon$ transitions ignored.

Epsilon transitions are a matter of convenience and can always be eliminated by the following process. For each state $q_1 \in Q$ we compute the set of all states $q_2$ reachable from $q$ along the edges with $\epsilon$ transitions, and add the outgoing non-epsilon edges of $q_2$ as outgoing edges of $q_1$ . We also insert $q_1$ into $F$ whenever one of the states $q_2$ is in $F$ . The resulting automaton accepts the same langauge and has no $\epsilon$ transitions.