2 ms·
Technically, a CFG is the intersection of an n-balanced parentheses language and a regular language. Therefore, any regular language can be described by a CFG
by baddox 17y ago
Technically, a CFG is the intersection of an n-balanced parentheses language and a regular language. Therefore, any regular language can be described by a CFG (but obviously not vice-versa).
I am completely unfamiliar with Perl and its regular expressions, but from your article and this comment I get the impression that they are Turing-complete, which would mean they're capable of describing any formal language as well as doing any "doable" computation. Is that correct?
- pkrumins 17y agoJust found this comment. I am not exactly sure if they are Turing-complete. The code in (??{code}) can be anything, so I guess, they are.