Re: Regex refresher

Spend a few minutes figuring out, for instance, the ten shortest strings that it'll match

Here are the first 12

""
"0"
"00" "11"
"000" "101" 
"0000" "1111" "1001" "1111"
"00000" "10101"
[download]

Bonus points if you notice a pattern in the set of strings that it matches....

All the strings are reversable?

(I'm assuming that anchors were implied.)

Comment on Re: Regex refresher Download Code

Replies are listed 'Best First'.
Re(2): Regex refresher by FoxtrotUniform (Prior) on Sep 13, 2002 at 07:46 UTC
`"" "0" "00" "11" "000" "101" "0000" "1111" "1001" "1111" "00000" "10101"` [download] 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 `(010)` 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. %-) `-- F o x t r o t U n i f o r m Found a typo in this node? /msg me The hell with paco, vote for Erudil!`	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re(2): Regex refresher
by FoxtrotUniform (Prior) on Sep 13, 2002 at 07:46 UTC

 ""
  "0"
  "00" "11"
  "000" "101" 
  "0000" "1111" "1001" "1111"
  "00000" "10101"
[download]

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. %-)

-- F o x t r o t U n i f o r m Found a typo in this node? /msg me The hell with paco, vote for Erudil!

[reply]
[d/l]
[select]

In Section Meditations