wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> RegEx: divisible by 3
        
(Message started by: william wu on Feb 26^th, 2003, 3:28am)

Title: RegEx: divisible by 3
Post by william wu on Feb 26^th, 2003, 3:28am

Construct a finite state machine (or equivalently, write a regular expression) which accepts all strings over the alphabet {0,1} which are divisible by 3 when interpreted in binary.

Note 1: There is a one-to-one correspondence between Regular Expressions and Finite State Machines. If you think you can solve the problem more easily by writing a regular expression, go ahead. However, a state machine approach will probably be more intuitive, and the solution will be more understandable.

Note 2: When scanned from left to right, the string is interpreted as moving from most significant bit to least significant, as expected.

Title: Re: RegEx: divisible by 3
Post by towr on Feb 26^th, 2003, 8:51am

..[hide]
once a prefix is divisible by three the number is divisible by three if the rest is divisible by three (so you can then ignore the prefix).

And for the rest you can just work mod 3.

So three states a0, a1 and a2, and transitions
a0 -0-> a0
a0 -1-> a1
a1 -0-> a2
a1 -1-> a0
a2 -0-> a1
a2 -1-> a2

a0 is the starting state, and the only end state
[/hide]..

Title: Re: RegEx: divisible by 3
Post by towr on Feb 26^th, 2003, 9:13am

regular expression: ... [hide]{0, [1, [0, 1*, 0]*,1]}*[/hide] ...
Finite State Machine (klick here) (http://wodan.let.rug.nl/vannoord_bin/fsagif?imgdotlr&%7B%7B0%2C+%5B1%2C+%5B0%2C+1*%2C+0%5D*%2C1%5D%7D*%7D)