http://blogs.msdn.com/b/ericlippert/archive/2005/12/15/regular-expressions-from-scratch-part-nine-a-dream-of-a-machine.aspxI want to come up with the simplest possible device that can identify whether a given string is a member of a given regular language. We need some kind of computer, but to make it easy to analyze, I want to put as many restrictions upon it as possibleen-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875)http://blogs.msdn.com/b/ericlippert/archive/2005/12/15/regular-expressions-from-scratch-part-nine-a-dream-of-a-machine.aspx#543296Sat, 04 Mar 2006 02:29:41 GMT91d46819-8472-40ad-a661-2c78acb4018c:543296Dan Sellers's WebLogWhen it comes to validating input regular expression becomes a very important part of your security plan.&amp;amp;nbsp;...<img src="http://blogs.msdn.com/aggbug.aspx?PostID=543296" width="1" height="1">http://blogs.msdn.com/b/ericlippert/archive/2005/12/15/regular-expressions-from-scratch-part-nine-a-dream-of-a-machine.aspx#536729Wed, 22 Feb 2006 12:18:28 GMT91d46819-8472-40ad-a661-2c78acb4018c:536729Synesthesia » Links Roundup for 2006-02-21PingBack from <a rel="nofollow" target="_new" href="http://www.synesthesia.co.uk/blog/archives/2006/02/22/links-24/">http://www.synesthesia.co.uk/blog/archives/2006/02/22/links-24/</a><img src="http://blogs.msdn.com/aggbug.aspx?PostID=536729" width="1" height="1">http://blogs.msdn.com/b/ericlippert/archive/2005/12/15/regular-expressions-from-scratch-part-nine-a-dream-of-a-machine.aspx#504697Fri, 16 Dec 2005 20:03:06 GMT91d46819-8472-40ad-a661-2c78acb4018c:504697Eric LippertWait for it... <br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=504697" width="1" height="1">http://blogs.msdn.com/b/ericlippert/archive/2005/12/15/regular-expressions-from-scratch-part-nine-a-dream-of-a-machine.aspx#504696Fri, 16 Dec 2005 20:01:00 GMT91d46819-8472-40ad-a661-2c78acb4018c:504696Jonas GrumbyIs there an algorithm to go from a DFA description of a language to a regular expression that describes the language?<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=504696" width="1" height="1">http://blogs.msdn.com/b/ericlippert/archive/2005/12/15/regular-expressions-from-scratch-part-nine-a-dream-of-a-machine.aspx#504306Thu, 15 Dec 2005 22:45:36 GMT91d46819-8472-40ad-a661-2c78acb4018c:504306Eric LippertWhoops, yes, you guys are correct. I'll emend the text. <br> <br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=504306" width="1" height="1">http://blogs.msdn.com/b/ericlippert/archive/2005/12/15/regular-expressions-from-scratch-part-nine-a-dream-of-a-machine.aspx#504293Thu, 15 Dec 2005 22:28:08 GMT91d46819-8472-40ad-a661-2c78acb4018c:504293Lee FeigenbaumYes, the language in question should really be: <br> <br>All strings with no b's and an odd number of a's AND all strings with an even number of a's following the final b in the string. <br> <br>Why? <br> <br>a's cause the machine to flip between the two states, so in the absence of any b's an odd number of a's is needed to get the machine to state 1. <br> <br>All b transitions, though, leave the machine in an acceptable state, regardless of what happened before. Thus, if we see at least one b, we're only interested in what happens after the last b in the string. Again, since a's toggle the state, pairs of a's leave the state unchanged, and so if we have a b then we require an even number of a's to follow the last b in the string. <br> <br>Lee <br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=504293" width="1" height="1">http://blogs.msdn.com/b/ericlippert/archive/2005/12/15/regular-expressions-from-scratch-part-nine-a-dream-of-a-machine.aspx#504267Thu, 15 Dec 2005 21:54:25 GMT91d46819-8472-40ad-a661-2c78acb4018c:504267Lance FisherAlso, wouldn't any odd number of a's be acceptable? Such as &quot;aaa&quot;: <br> <br>(0,a) -&gt; 1 <br>(1,a) -&gt; 0 <br>(0,a) -&gt; 1<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=504267" width="1" height="1">http://blogs.msdn.com/b/ericlippert/archive/2005/12/15/regular-expressions-from-scratch-part-nine-a-dream-of-a-machine.aspx#504224Thu, 15 Dec 2005 20:51:29 GMT91d46819-8472-40ad-a661-2c78acb4018c:504224Scott PedersenIn addition to &quot;every string is either a or anything ending in b&quot; would not any sting ending with series of a of even length also be acceptible? That is, baaaa would seem to be accetpable as well. <br> <br>Just making sure I haven't missed anything in my understanding of your DFA.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=504224" width="1" height="1">