NFA vs. DFA « Chad Salinas Computer Science Scratch Pad

NFA vs. DFA

Theorem: $\forall$ NFA, $\exists$ a DFA that recognizes the same language.

Of course iff proofs require bi-direction, even when one direction is trivial.

Has it really been that long ago??? Just give me a state and a symbol so I can union it with the existing states…

Don’t forget about $\epsilon$ transitions.

This entry was posted on Monday, July 30th, 2007 at 11:26 pm and is filed under Automata & Complexity Theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.