Lab for Automated Reasoning and Analysis 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] (current)
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.
  
 
finite_state_machine_with_epsilon_transitions.txt · Last modified: 2008/05/14 10:22 by vkuncak
 
© EPFL 2018 - Legal notice