comment on

 ""
  "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!

In reply to Re(2): Regex refresher by FoxtrotUniform
in thread Regex refresher by FoxtrotUniform

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


Problems? Is your data what you think it is?
	PerlMonks