Finite State Machines

Todays tid-bit is about FSM (Finite State Machines) of which there are

NFA-E  Non-deterministic Finite Automaton - With E closure
NFA Non-deterministic Finite Automaton   explanation
DFA Deterministic Finite Automaton explanation

So I was doing my homework and then I came across a question about stating why a FSM has to be a DFA in order to have the complement of the FSM to recognize everything of the alphabet the original DFA cannot.

So after some investigation here is WHY you have to convert any NFA to a DFA for it to hold true for all complements.

Proof by counter example:

A final state has 2 circles around it
A non-final state has 1 circle around it
Arrows are transitions

When you take the complement of a FSM you do not change transitions, rather you change all final states to non-final states, and all non-final states to final. This allows for a Complement to handle anything from the alphabet the original couldn't.
So it becomes:
Final states: S0, S2, S4
Non-Final States: S3, S1

HOWEVER the input "E" will still be accepted by the complement, and thus both original and complement FSM will take same input breaking the rules of a complement! Therefore you NEED to have a DFA.

I hope you understood this! If you have a question/comment post it below. Thanks for reading!