Monks,

I came across this regex in my compilers course. It isn't particularly advanced, in terms of Perl's regex capabilities, but it's complex enough to give pause to most of the students in this (fourth-year undergraduate) course. Spend a few minutes figuring out, for instance, the ten shortest strings that it'll match:

/^(0|1(01*0)*1)*$/

[download]

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

Update: Silly me. In the context of this course, regexes describe languages, they don't match strings. In that context, anchors aren't useful. (Finite Automata match strings, and you can build FAs from regexes automatically.) But I brought this example over to a Perl context, and played with the terminology just a bit to make it friendlier... and slipped up. Anchors added, thanks to all who pointed it out.

--
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 Regex refresher by FoxtrotUniform

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.