Complement of Finite State Automata

Algorithm

  1. Make the FSA deterministic (see relevant section).
  2. If the FSA is partial, make it total (see relevant section).
  3. Copy the FSA but all states which were final are now made non-final and vice-versa.

Example

Consider the following FSA:

  1. The FSA is already deterministic.
  2. Make the FSA total:

  3. and swap final and non-final states:

Exercises

Construct FSA which recognise the complement of the following languages described using FSA: