Create a new account
I've added an interesting extension to the syntax. Would this be a good idea for Perl?
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
(FWIW, I've been vaguely angling for an argument based on the Chomsky-Schützenberger theorem.)
Get More Comments