in reply to Are Perl patterns universal?
Do you mean, given an arbitrary Turing machine, can you build a regex $foo such that $x =~ /$foo/ if and only if $x is accepted by the Turing machine? Using just lookaheads/lookbehinds and captures/backreferences, I'd definitely say no. You don't even get all CFLs this way (consider {a^n b^n : n > 0}) but yet you get some CSLs (consider {a^n b a^n b a^n : n > 0}). See also Perl regular expressions vs. RL, CFL, CSL.
A Turing machine must have unbounded memory. A Perl regex using only captures & backreferences has a bounded (linear in the size of input) amount of "memory" about the its input  the number of captures is fixed when the regular expression is compiled, and each capture contains at most the entire string. Not only that, but the type of access to this memory is very stricly limited: you can only match substrings. In addition, you don't have write access to this memory in any sort of arbitrary fashion (apart from trying a different substring of the input  which is hardly arbitrary, and could be viewed as just a form of nondeterminism). This is an essential feature for the power of a Turing machine.
Even allowing (??{$re}) just gets you all CFLs (and various closures  intersection and complement, etc), but doesn't allow for universal behavior because the unbounded memory just isn't there.
To do most "interesting" things with regexes, you'll need a layer of Perl around (or inside) the regex, to do either iterated substitutions, multiple matches, or build a different regex for each input. The last approach is a fun one used by various regexreductions: Hamiltonian Cycle, 3SAT, NQueens.
blokhead


Replies are listed 'Best First'.  

Re^2: Are Perl patterns universal?
by sleepingsquirrel (Hermit) on Nov 09, 2004 at 17:30 UTC  
by blokhead (Monsignor) on Nov 09, 2004 at 20:39 UTC 