Re: [SPOILER] Perl 'Hard' Quiz of the Week #2005-03-22

On Fri, Mar 25, 2005 at 10:19:47AM -0600, Greg Bacon wrote:
> Somehow I noticed that reversing the directions of the transitions
> seemed to accept the reversed language but lost the property of
> tracking remainders.
> 
> Testing seems to show this to be a valid approach, and I wish I knew
> why.  I need to look through the Linz book to see if this is a property
> of regular languages.

Well, it's not true for regular languages in general (it only works if
each state has exactly one 0-arc and one 1-arc in (and of course one
0-arc and one 1-arc out)). That's true for this FSM but not in general.

I'll try to explain why it works in this case. It's relatively easy to
me, because I did most of the work when I developed my two solutions. I
didn't try the MSB variant and so I didn't notice thar reverse-trick.
But now, I even know why it works ;)

The interpretation of the MSB version is the following. Each state is
the remainder of the number we read till now. If read a "0", our number
is doubled, if read a "1" it's doubled and increased by one. Because
each number x can be written as x = n*k + r, r < n (r is the remainder),
this transition has the same effect on the remainder (we all know this,
an that's why the MSB version is so easy). The transition is:

  p --0--> 2p   mod n
  p --1--> 2p+1 mod n

What can we say about the LSB version? Now we can't just use the
remainder as hint. We must know a second variable.

Suppose the number we read till know is "x = m*n + p" (p is the
remainder). The next bit arriving will increase x by 2^k. In general we
can write: 
  
  x = m*n + p + b0*2^(k+0) + b1*2^(k+1) + b2+2^(k+2) + ...
    = m*n + p + 2^k*(b0 + b1*2^1 + b2+2^2 + ...)
    = m*n + p + q*(b0 + b1*2^1 + b2+2^2 + ...), q = 2^k

the "bi" are the following bits. What we want know is if x = 0 mod n if 
the next bit (b0) is 0 or 1. Since 

  n | m*n + p + q*(...) <=> n | p + q*(...) 

we only need to know p and q. If a 0 arrives, nothing changes but we can
put one more 2 into q:

  p + q * (0 + b1*2^1 + b2 * 2^2 + ...) = p + (2q)*(b1 + b2*2^1 + ...)
    
If a 1 arrives, we put one more 2 into q and the first addend into p:
  
  p + 1*q + q * (0 + b1*2^1 + b2*2^2 + ...) = 
    (p + q) + (2q)*(b1 + b2*2^1 + ...)

If p = 0 mod n, we know that the number we read till know is divisible
by n. So we have again a relatively simple transition:

  (p,q) --0--> (p, 2*q) mod n
  (p,q) --1--> (p+q, 2*q) mod n

This was the idea for my first solution: create one state for each pair
of (p,q) and the corresponding connections. As I said already, several
pairs of (p,q) are equivalent. We know have to know if two pairs (p,q)
and (p',q') are equivalent. So first we have to specify what we mean by
"equivalent". Two states are equivalent if the same following bits lead
either to an accepting state or a not-accepting state. Let's take a look
what happens with (p,q) if some bits arrive:

    (p,q) --0--> (p,2q) --1--> (p+2q,4q) --1--> (p+6q,8q) ....
or  (p,q) --1--> (p+q,2q) --1--> (p+3q,4q) --0--> (p+3q,8q) ...

Our goal is to reach a (0,z) state, because this are the accepting
states (p = 0 <=> remainder = 0 <=> n|x).

So we can say, two pairs are equivalent if

  (p,q) ~ (p',q') :<=> p + kq = p' + k'q' = 0 mod n, k = k' mod n

And this leads to the clever transition for n states:
There are n possible values for k (k = 0,..,n-1). For each k we have
to choose one pair (p,q): p + k*q = 0 mod n, do the transition, get 
a pair (p',q') and calculate k': p' + k'q' = 0 mod n. This k' is our
next state.

It doesn't matter what pair (p,q) for a given k we choose, so we take
the simplest one: (n-k, 1). This is correct because 

  (n-k) + k*1 = n = 0 mod n

Know do the transition:

  (n-k, 1) --0--> (n-k,2)

Now find k': (n-k) + k'*(2*1) = 0 mod n
Because n is odd => gcd(2,n) = 1 => there is an y: 2*y = 1 mod n and
it's easy to so that y = (n+1)/2. So solve this equation:

  (n-k) + 2k' = 0 mod n <=>
  2k' = -n+k = k mod n <=>
  k' = 2^-1 * k = (n+1)/2 * k mod n
  
Doing the same for the second transition leads to:
  (n-k, 1) --1--> (n-k+1, 2)
  k' = (n+1)/2 * (k-1) mod n

So we have our final transition:

  k --0--> k * (n+1)/2 mod n
  k --1--> (k-1) * (n+1)/2 mod n

And that's all we need to see why we just need to reverse the
transitions:

  p' = 2p mod n <=> p' * (n+1)/2 = p mod n

and
  
  p' = 2p+1 mod n <=> (p'-1) * (n+1)/2 = p mod n

(remeber 2^-1 = (n+1)/2 = mod n)

And because that's such a long way I said, it was a difficult task for
me, although I'm sure that there is a much shorter solution ;)

btw: it doesn't matter if you write for the --1--> transition:

  (k-1) * (n+1)/2 
or
  (k+1) * (n+1)/2

because the transition-function f: P x Q x {0,1} -> P x Q 
is not unique. All it must do is to make sure that:

[ (p,q) ~ (p',q') ] <=> [f(p,q,c) ~ f(p',q',c)] for all p,q,c

and if you choose

(p,q) --1--> (p-q, 2q) mod n

you get the (i+1)-variant, but I didn't check this in more detail ;)



Bye,

	Frank Fischer





-- 
eMail: frank.fischer-JJ2xi2hz/[email protected] 
Jabber: lyro-/[email protected]
ICQ: 49470926
freebits.de - Linux, Unix && OpenSource