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.

use Perl

All the Perl that's Practical to Extract and Report

Regex power! More | Login | Reply

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Without JavaScript enabled, you might want to use the classic discussion system instead. If you login, you can remember this preference.

Proof of context-free-ness (Score:1)

by 2shortplanks (968)

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
- Re:Proof of context-free-ness (Score:1)
  
  by robin (1821)
  
  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.)

Get More Comments

Stories, comments, journals, and other submissions on use Perl; are Copyright 1998-2006, their respective owners.