Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | |||
finite_state_machine_with_epsilon_transitions [2007/05/10 12:02] vkuncak |
finite_state_machine_with_epsilon_transitions [2008/05/14 10:22] vkuncak |
||
---|---|---|---|
Line 11: | Line 11: | ||
An execution is now an alternating sequence of states and elements of $\Sigma \cup \{\epsilon\}$. 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 $\epsilon$ transitions ignored. | An execution is now an alternating sequence of states and elements of $\Sigma \cup \{\epsilon\}$. 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 $\epsilon$ transitions ignored. | ||
- | Note: generalization to strings | + | Note: we could further generalize to allow arbitrary strings |
=== Eliminating epsilon transitions === | === Eliminating epsilon transitions === | ||
+ | |||
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_1$ along the edges with $\epsilon$ transitions. We then add the outgoing non-epsilon edges of all such $q_2$ to the existing 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. | 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_1$ along the edges with $\epsilon$ transitions. We then add the outgoing non-epsilon edges of all such $q_2$ to the existing 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. | ||