LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

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.