Newsgroups: rec.puzzles
From: hoey@ai.etl.army.mil (Dan Hoey)
Date: 25 Sep 90 18:07:22 GMT
Subject: Re: Finite Automata puzzle

dschm...@athena.mit.edu (Dan Schmidt) writes:

>The alphabet for this finite automaton consists of pairs of binary
>digits, e.g. 0/0 or 0/1 or 1/0 or 1/1.

The bit before the slash is from a binary number x and the bit after
the slash is from a binary number y.

>... The digits are read with the least significant bit first.  Thus if x were
>6 [110 in binary] and y were 25 [11001 in binary], the input sequence would be
>0/1 1/0 1/0 0/1 0/1

>The problem: construct a finite automaton with the given alphabet
>which accepts an input sequence only if y = 5x.

Solution follows:

Let the states be 0, 1, 2, 3, 4, and F.  State 0 is the initial and
the only accepting state.  The transition from state S on input xi/yi
is to state

  (S + 5 xi - yi)/2

provided the latter is an integer.  All other transitions, including
those from state F, are to state F.  For the numerically impaired, the
transition table is

     Input:  0/0   0/1   1/0   1/1
State
  0           0     F     F     2
  1           F     0     3     F
  2           1     F     F     3
  3           F     1     4     F
  4           2     F     F     4
  F           F     F     F     F

The inductive invariant needed to prove this recognizes the proper
language is that initial strings x0 and y0 of length n leave the
machine in state
  (5 x0 - y0)/2^n
if the latter is an integer, otherwise state F.

Dan