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!

Useful CS Links

Hey guys! Me here again, here are some helpful links:


http://stackoverflow.com/
For all your CS programming related questions, c++, vb, javascript, java, c#, etc. Be careful what you ask though, their ban on questions is quite extensive, they really hate "dumb" questions.

http://math.stackexchange.com/   Similar: http://mathoverflow.net
Same as above but for math.

http://serverfault.com
""" But for servers..

http://superuser.com
""" for random tech questions

http://www.w3schools.com/
A website to teach you everything that you need to know to create a website from HTML to XML to PHP and AJAX. (To be honest, I'm only vaguely knowledgeable about these topics, I'm actually educating myself using this site haha)

http://codingbat.com/
For learning Java, and now offers Python education. Good for introduction and even "medium" level topics such as advanced recursion.