laziness, impatience, and hubris | |
PerlMonks |
Re(2): Regex refresherby FoxtrotUniform (Prior) |
on Sep 13, 2002 at 07:46 UTC ( [id://197465]=note: print w/replies, xml ) | Need Help?? |
I regret to inform you that 101 is not matched, though 110 and 011 are. (abell's solution is correct.) I'm a bit gratified that people seem to be having a fairly difficult time with this (must be the (01*0)* 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. 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. %-) --
In Section
Meditations
|
|