comment on

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

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.


Come for the quick hacks, stay for the epiphanies.
	PerlMonks