Differences
This shows you the differences between two versions of the page.
| Next revision Both sides next revision | |||
|
finite_state_machine_with_epsilon_transitions [2007/05/05 18:21] vkuncak created |
finite_state_machine_with_epsilon_transitions [2007/05/05 18:22] vkuncak |
||
|---|---|---|---|
| Line 7: | Line 7: | ||
| 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. | 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. | + | 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. |