# Differences

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

 finite_state_machine_with_epsilon_transitions [2007/05/10 12:02]vkuncak finite_state_machine_with_epsilon_transitions [2008/05/14 10:22] (current)vkuncak Both sides previous revision Previous revision 2008/05/14 10:22 vkuncak 2007/05/10 12:02 vkuncak 2007/05/05 18:22 vkuncak 2007/05/05 18:21 vkuncak created 2008/05/14 10:22 vkuncak 2007/05/10 12:02 vkuncak 2007/05/05 18:22 vkuncak 2007/05/05 18:21 vkuncak created 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.