Definition: Let M = (Q, S, R, s, F) be an e-free FA. M is a deterministic finite automaton (DFA) if for each rule pa ® q Î R it holds that R – {pa ® q} contains no rule with the left-hand side equal to pa.
From FA to DFA in Essence 2/2
 2) Gist: Removal of nodeterminism
a
...
...
...
p
q1
q2
a
p
a
{q1, q2}
...
...
New State
5/44