next up previous
Next: Minimization Up: Operations on recognizers Previous: Determinization

Complementation

If the determinizer also maintains the empty subset of states (cf. the last line in the previous example), then the resulting determinized automaton is complete: for each state a transition is applicable for each symbol of the alphabet. This property is important in order to define complementation. If an automaton M1 with final states $F\subseteq Q$ is deterministic and complete, then an automaton accepting the language $\overline{L(M_1)}$ is obtained from M1 simply by replacing F with Q-F.

As usual, the difference operation is defined straightforwardly in terms of complementation and intersection: if A and B are regular languages, then A-B is defined as $A \wedge \overline{B}$.



Noord G.J.M. van
2001-06-22