Welcome to the Monastery | |
PerlMonks |
Re^4: check for square-number with a regexby moritz (Cardinal) |
on Oct 23, 2009 at 15:47 UTC ( [id://802930]=note: print w/replies, xml ) | Need Help?? |
First of all sorry for getting the numbering wrong, I misremembered REG as being Typ-0 and Turing as being Typ-3, it's the other way round. What's another example of Perl regexes recognising a language that a CFG can't?m/^(\w+)\1$/ Is already outside CFG. CFG is parsed by a non-deterministic finite automaton which has access to a stack of infinite size. Since it can only access the top element of the stack, it has only access to the capture in reverse order, or with a finite look-behind on the stack (implemented by storing some values in the state of the NFA). A more formal proof can be made with the Pumping lemma for context-free languages. I also think that the regex primality test is outside of CFG, but I've never proven that, so don't rely on it ;-)
In Section
Seekers of Perl Wisdom
|
|