Differences
This shows you the differences between two versions of the page.
Last revision Both sides next revision | |||
determinization_of_finite_state_machine [2007/05/05 17:17] vkuncak created |
determinization_of_finite_state_machine [2007/05/05 17:18] vkuncak |
||
---|---|---|---|
Line 3: | Line 3: | ||
For every [[finite state machine]] $A = (\Sigma,Q,\Delta,q_0,F)$ there exists a deterministic finite state machine that accepts the same language. | For every [[finite state machine]] $A = (\Sigma,Q,\Delta,q_0,F)$ there exists a deterministic finite state machine that accepts the same language. | ||
- | This machine is given by $A_D = (\Sigma,2^Q,\Delta_D,\{q_0\},F_D)$ where $\Delta_D = \{ (Q_1,a,Q_2) \mid Q_2 = \Delta_{run}(Q_1,a) \}$ and $F_D = \{ S \mid S \cap F \neq \emptyset \}$. | + | This machine is given by $A_D = (\Sigma,2^Q,\Delta_D,\{q_0\},F_D)$ where |
+ | * $\Delta_D = \{ (S,a,\Delta_{run}(S,a)) \mid S \subseteq Q, a \in \Sigma \}$ | ||
+ | * $F_D = \{ S \mid S \cap F \neq \emptyset \}$. | ||