LARA

Differences

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

Link to this comparison view

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 \}$.