Deterministic and Non-Deterministic Automaton

If we restrict the transition relation $\Delta$ such, that for each pair (q,a) $in$ Q $\times$ $\Sigma^{*}$ there is at most one q' $in$ Q as successor state and we set $\mid$I$\mid$ = 1 then we have a deterministic finite automaton (DFA). Otherwise the automaton is non-deterministic finite automaton (NFA).

THEOREM: For each finite automaton there exists a deterministic and complete one recognizing the same set.

PROOF: Cf. Perrin (1990) [227], P.6.

CORROLARY: The complement of a recognizable set is again a recognizable set.

PROOF: Cf. Perrin (1990) [227], P.6.