Complement of Finite State Automata
Algorithm
- Make the FSA deterministic (see relevant
section).
- If the FSA is partial, make it total (see relevant
section).
- Copy the FSA but all states which were final are now made
non-final and vice-versa.
Example
Consider the following FSA:
- The FSA is already deterministic.
- Make the FSA total:
- and swap final and non-final states:
Exercises
Construct FSA which recognise the complement of the
following languages described using FSA:
-
-