#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$/);

##</code><code>##

#match context sensitive grammar --[0{N}1{N}2{N}] (012, 001122, 000111222, ...)
$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$/);

##</code><code>##

#Word boundries are zero-width so the regex engine will never progress

my $inf; $inf=qr/\b(??{$inf})/;

##</code><code>##

#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";


##</code><code>##

#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)]} ";
}