![\"\"](\"https:\/\/i0.wp.com\/scientopia.org\/blogs\/goodmath\/files\/2011\/04\/dfa.png?resize=476%2C263\" "\\"dfa\\"")
<\/a><\/p>\n We start with 
. From , if we see an “a”, there are three things that could happen. Either we’d take the transition to 
, or we’d take the empty transition to 
, and then take the transition from to , or we’d take the empty transition to , and then take the a-transition to 
. So in the DFA, we’d have an a-transition from 
to 
. <\/p>\n
If we saw a 
, there are no transitions shown. By convention, we assume some “invisible” states. Any time that there’s no transition listed for a given input symbol from a state, we assume that there’s a transition from the state to “error”. But we can use that assumption in the DFA as well as the NFA – so we just won’t show the error state or transitions – that makes our machines much easier to read.<\/p>\n
Analyzing state has given us state . If we see an input of a, that could bring us to or (if the NFA was in state ); or it could bring us to state (if the NFA was in state .) So for an input of a, we’d put a transition to state 
. If we saw an input\tof “b”, we could either go from to , or\tfrom to . So for b, we’d have a transition to 
.<\/p>\n
And so on – the final result being:<\/p>\n
What does this mean?<\/em> <\/p>\n Well, a NFA isn’t more powerful than a deterministic machine (a DFA<\/em>)- there’s nothing that an NFA can do that a DFA can’t. But the NFA can do it with a lot<\/em> fewer states. The DFA is a lot more complicated; it can have exponentially more states. But for an NFA, there’s a corresponding DFA that can recognize the same language.<\/p>\n Most importantly… it means that with a fixed, finite amount of state, non-determinism doesn’t buy you any computational power. With a finite state machine, non-determinism can’t doesn’t even make it possible to do anything faster! The only benefit that non-determinism has at this level is space: the amount of state that you need (that is, the number of states in the machine) can be smaller with a non-deterministic machine.<\/p>\n","protected":false},"excerpt":{"rendered":"
In the last post, I mentioned the fact that regular expressions specify the same set of languages as regular grammars, and that finite state machines are the computational device that can recognize those languages. It’s even pretty easy to describe how to convert from regular expressions to FSMs. But before we do that, to make […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[79],"tags":[107,132,156,204],"class_list":["post-1389","post","type-post","status-publish","format-standard","hentry","category-computation","tag-automata","tag-computation-2","tag-finite-state-machines","tag-non-determinism"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-mp","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1389","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=1389"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1389\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=1389"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=1389"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=1389"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"\"](\"https:\/\/i0.wp.com\/scientopia.org\/blogs\/goodmath\/files\/2011\/04\/nfa.png\" "\\"nfa\\"")
<\/a><\/p>\n