Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re: Regular Expreso 2

by oiskuu (Hermit)
on Apr 27, 2016 at 17:29 UTC ( [id://1161674]=note: print w/replies, xml ) Need Help??


in reply to Regular Expresso 2

Multiplying by three is the same as shift + add. Essentially you have a binary adder with carry, or rather two carries: the input bit is also a carry. So you have an FSM with three states for the three possible carry values 0, 1, 2.

    00111
 +   00111
  --------
     10101

Let's start with a recursive regex with groups for each of the states.

qr/ (?(DEFINE) ( 00 (?1) | 11 (?2) | ) # group 1: carry = 0 ( 01 (?1) | 10 (?3) ) # group 2: carry = 1 ( 00 (?2) | 11 (?3) ) # group 3: carry = 2 ) \A(?1)\Z /x;
From here, we can inline the group 2 in g1 and g3:
qr/ (?(DEFINE) ( 00 (?1) | 11 01 (?1) | 11 10 (?3) | ) ( ) ( 00 01 (?1) | 00 10 (?3) | 11 (?3) ) ) \A(?1)\Z /x;
Now it should be obvious that the group 3 i.e. carry=2 state is entered with a 11 10 and left with 00 01. Rewriting the regex with repeats instead of recursion:
my $Regex_Pattern = qr/ \A ( 00 | 11 01 | 11 10 ( 00 10 | 11 )* 00 01 )* \Z /x;

ps. I'm assuming that the input string must have 2*n digits.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1161674]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others contemplating the Monastery: (4)
As of 2024-03-29 10:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found