Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • Okay, I think you're making my brain flow out of my ears. Ow.

    You're right about it being able to match anything that a context-free grammer can match. By allowing recursion you're adding a stack to your traditional regular expression engine - basically a Finite State Automata with a stack. This is what is known as a Push Down Automata.

    Take a look at section 3.4 of the second edition of The Elements Of The Theory of Computation [amazon.co.uk] which proves that "The class of langauges accepted by pushdown automata is exactly the class of context-free langauges".

    • Interesting. The bit that wasn't (and still isn't) obvious to me is that the limited kind of stack storage provided by recursion is as powerful as a full PDA. On the face of it, a PDA has more freedom with its stack. Is there a simple argument to show that it doesn't really?

      (FWIW, I've been vaguely angling for an argument based on the Chomsky-Schützenberger theorem.)