note
FoxtrotUniform
<ul>
<code>
""
"0"
"00" "11"
"000" "101"
"0000" "1111" "1001" "1111"
"00000" "10101"
</code>
</ul>
<p>I regret to inform you that 101 is not matched, though
110 and 011 are. ([abell]'s solution is correct.)</p>
<p>I'm a bit gratified that people seem to be having a
fairly difficult time with this (must be the
<code>(01*0)*</code> group in the middle of the right-hand
alternative; I think people tend to see the 01 as both bound
by the *, rather than just the 1): means it's a useful
example.</p>
<p>Oh, and the completeness proof for this regex matching
multiples of three is fairly straightforward, once you have
a minimal DFA for matching this regex. (In short: your
minimal DFA has three states, each corresponding to a
modulus of 3. 0 is the only accepting state, and you can
prove by contradiction that all multiples of 3 end up in
the 0 state.) Maybe I'll write it up when my profs stop
assigning me papers. %-)</p>
<p><tt>-- <br>
<font color="#000000">F</font>
<font color="#220000">o</font>
<font color="#550000">x</font>
<font color="#880000">t</font>
<font color="#aa0000">r</font>
<font color="#dd0000">o</font>
<font color="#ff0000">t</font>
<font color="#ff0000">U</font>
<font color="#dd0000">n</font>
<font color="#aa0000">i</font>
<font color="#880000">f</font>
<font color="#550000">o</font>
<font color="#220000">r</font>
<font color="#000000">m</font><br>
Found a typo in this node? /msg me<br>
The hell with [paco], vote for [Erudil]!
</tt></p>
197155
197159