LARA

This is an old revision of the document!

Determinization of finite state machine

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