Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
finite_state_machine_with_epsilon_transitions [2007/05/05 18:22] vkuncak |
finite_state_machine_with_epsilon_transitions [2008/05/14 10:22] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Finite state machine with epsilon transitions ====== | ====== Finite state machine with epsilon transitions ====== | ||
| + | |||
| + | === Definition === | ||
| Finite state machine with epsilon transitions is an extension of a [[finite state machine]] where transitions can be labelled by $\epsilon$. If such a transition $(q_1,\epsilon,q_2)$ exists then an automaton may transition from $q_1$ to $q_2$ without consuming any portion of the input string. | Finite state machine with epsilon transitions is an extension of a [[finite state machine]] where transitions can be labelled by $\epsilon$. If such a transition $(q_1,\epsilon,q_2)$ exists then an automaton may transition from $q_1$ to $q_2$ without consuming any portion of the input string. | ||
| Line 5: | Line 7: | ||
| As for finite state machine, we define a finite state machine with epsilon transitions as a 5-tuple $A = (\Sigma,Q,\Delta,q_0,F)$ with the only difference that $\Delta \subseteq Q \times (\Sigma \cup \{\epsilon\}) \times Q$ where $\epsilon \notin \Sigma$ is a special symbol. | As for finite state machine, we define a finite state machine with epsilon transitions as a 5-tuple $A = (\Sigma,Q,\Delta,q_0,F)$ with the only difference that $\Delta \subseteq Q \times (\Sigma \cup \{\epsilon\}) \times Q$ where $\epsilon \notin \Sigma$ is a special symbol. | ||
| - | 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. | + | === Execution of machine with epsilon transitions === |
| + | |||
| + | 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: we could further generalize to allow arbitrary strings | ||
| + | |||
| + | === 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. | ||