Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??

--or--

Why compute with anything else?

Lately I've been wondering about just how powerful Perl's pattern matching language is (commonly known as regular expressions). Because of backtracking and recursion, Perl's patterns can match more than regular languages. They can match (at least some) context-free grammars...
#match context free grammar --[0{N}1{N}] (e.g. 01, 0011, 000111, etc.) $cf = qr/01|0(??{$cf})1/; $init = "00001111"; print "match\n" if ($init=~m/^$cf$/);
...they can also match (at least some) context sensitive grammars...
#match context sensitive grammar --[0{N}1{N}2{N}] (012, 001122, 000111 +222, ...) $h=qr/01|0(??{$h})1/; $t=qr/12|1(??{$t})2/; $cs=qr/(?=$h 2+$)(?=0+$t$)/x; $init = "001122"; print "match\n" if ($init=~m/^$cs$/);
(I've haven't proven those two snippets correct, so any counter examples would be appreciated)

We can also craft patterns that loop forever (not merely a long time) (well, ignoring stack overflows that is)

#Word boundries are zero-width so the regex engine will never progress my $inf; $inf=qr/\b(??{$inf})/;
On a more mundane level we can also compute simple things...
#simple computations with pattern matching operating on unary numbers $"=""; $_ = 'lll+ll'; #3+2 @add = m/(l+)\+(l+)/; print "$_ = @add\n"; $_ = 'lll*ll'; #3*2 @mult = m/l(?=.*\*(l*))/g; print "$_ = @mult\n"; $_ = 'lll'; @sqr = m/(l)(?=(l*))(?=(l*))/g; print "$_ squared = @sqr\n";
It is also known that certain cellular automata are universal (Rule 110), and with some additional machinery, we can get a regex to emulate one.
#implement rule 110 cellular automata $init = " X "; #initial value (pad with two spaces on either side) $"=""; for (1..24) { print ' ' x (38-$_)."$init\n"; $init=" @{[($init=~m/^(\s) | #Start of line (?<=\s)(\s)(?=\s) | #000 (?<=\s) \s (?=(X)) | #001 (?<=\s) (X)(?=\s) | #010 (?<=\s) (X) (?=X) | #011 (?<=X) (\s)(?=\s) | #100 (?<=X) \s (?=(X)) | #101 (?<=X) (X)(?=\s) | #110 (?<=X) X (?=X+(\s))| #111 (\s)$ #End of line /gx)]} "; }
Of course that might be considered cheating, because we've used an external mechanism for looping. It gets more interesting when we consider that some Diophantine equations are universal . And a few perl wizards have managed to use regex to solve linear Diophantine equations and test for primeness (see also section 6.16 of the Ram book).

Your mission, should you choose to accept it, is to meditate on this problem and see if you can enlighten the rest of us as to whether perl5 patterns are universal. (Or, as a lesser challenge, see if you can get a regex to compute 2**N, or factorial(N), or Ackermann's function)


-- All code is 100% tested and functional unless otherwise noted.

In reply to Are Perl patterns universal? by sleepingsquirrel

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (4)
As of 2024-03-29 05:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found