Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot

Re: Regex refresher

by dws (Chancellor)
on Sep 12, 2002 at 07:20 UTC ( #197159=note: print w/replies, xml ) Need Help??

in reply to 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"

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

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"

    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!

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://197159]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (5)
As of 2023-01-29 08:31 GMT
Find Nodes?
    Voting Booth?

    No recent polls found