Simple FSM
------ ---

Your company wants to implement a very simple Finite
State Machine (FSM) to recognize certain patterns in an
input bit stream.  For example, they want to know when
the last 7 bits are `1111110'.  This bit sequence is
used in a `flag' that separates data blocks, where the
data has been modified so that the flag bit sequence can
never occur within a data block.

You have been asked to write a basic FSM simulator.
Input is a string of bits.  States are labeled with
upper case letters or the special characters `$' and
`*'.

A simple example FSM description is:

	$ $ A
	A * A
	* $ A

which describes an FSM that is in state * when the last
2 bits read are `10'.

The 3 lines of this FSM description say:

    when in state $, on reading a 0 go to state $,
                 but on reading a 1 go to state A

    when in state A, on reading a 0 go to state *,
                 but on reading a 1 go to state A

    when in state *, on reading a 0 go to state $,
                 but on reading a 1 go to state A

For each state you are given two successor states, one
to go to if the next bit input is `0', and one to go to
if the next bit input is `1'.  The FSM starts in state
`$', and stops when there are no more bits to read.

If the FSM does what it is supposed to, it will be in
state `*' if and only if the last several bits read are
the pattern sought.
            
To see how this FSM executes when inputting the binary
string `010011001110011110', write the sequence of
states that the machine is in so that each state is
underneath the next bit to be read:

	0100110011100111100
	$$A*$AA*$AAA*$AAAA*$

This means that the FSM:

    starts in state `$'
    goes to state `$' upon reading the first `0'
    goes to state `A' upon reading the first `1'
    goes to state `*' upon reading the second `0'
    goes to state `$' upon reading the third `0'
    . . . . . . . . . .
    goes to state `A' upon reading the last `1'
    goes to state `*' upon reading the next to last `0'
    goes to state `$' upon reading the last `0'
    stops when there is no binary digit left to read

Similarly the FSM:

	$ $ A
	A $ B
	B $ C
	C * C
	* $ A

which is intended to recognize the pattern `1110'
executes as follows on the same input string:

	0100110011100111100
	$$A$$AB$$ABC*$ABCC*$


Input 
-----

For each of several test cases, the following in order:

    a line containing just the test case name
    lines containing the FSM description
    a line containing just `.'
    one or more input lines each containing
        a binary string
    a line containing just `.'

No line is longer than 80 characters.

Input ends with an end of file.

An FSM description consists of `state description lines'
each of the form:

	s z n

which says:

    when in state s, on reading a 0 go to state z,
                 but on reading a 1 go to state n

There are 28 FSM states ($, A, B, ..., X, Y, Z, *), but
unused states have no state description line.

Each binary string contains just `0's and `1's and is
processed independently of the other binary strings.


Output
------

For each test case, first an exact copy of the test
case name line, and then for each binary string input
line two lines:

    (1) an exact copy of the binary string input line
    (2) the state sequence of the FSM execution for
        the input binary string, as described above;
	here the state that the FSM is in just before
	reading a binary digit is placed directly under
	the binary digit

Note there is no whitespace in either of these two
lines.


Sample Input
------ -----

-- RECOGNIZE `10' --
$ $ A
A * A
* $ A
.
0000
1111
0100
010010100
0100110011100111100
.
-- RECOGNIZE `1110' --
$ $ A
A $ B
B $ C
C * C
* $ A
.
1111
1100
1110
1011
101010
010010100
0100110011100111100
0101101110111100
.


Sample Output
------ ------

-- RECOGNIZE `10' --
0000
$$$$$
1111
$AAAA
0100
$$A*$
010010100
$$A*$A*A*$
0100110011100111100
$$A*$AA*$AAA*$AAAA*$
-- RECOGNIZE `1110' --
1111
$ABCC
1100
$AB$$
1110
$ABC*
1011
$A$AB
101010
$A$A$A$
010010100
$$A$$A$A$$
0100110011100111100
$$A$$AB$$ABC*$ABCC*$
0101101110111100
$$A$AB$ABC*ABCC*$


Extra Notes (not relevant to solving problem):
----- -----  --- -------- -- ------- -------

The synchronous High Level Data Link Control (HDLC)
protocol for communications via synchronized bit
streams uses `01111110' as a `flag'.  Successive flags
are used to synchronize clocks and bracket data blocks,
which are altered so they cannot contain flags.  This is
done simply by inserting a 0 bit whenever 5 successive 1
bits have occurred in the data, and removing the 0 bit
when `111110' is received in data.  The flag contains 6
successive 1's; 7 successive 1's is considered to be a
transmission error.

All FSM's have the same structure except for input/out-
put.  As an example of a slightly more complicated in-
put/output structure, let the FSM output a character
when making a transition from one state to another.
So the description line `s z n' becomes `s z/Z n/N'
where Z and N are characters output when the next
state becomes z or n, and the output is optional, so
the `/Z' and `/N' are optional.  Using this you can
describe an FSM that will insert or remove the 0 bit
in HDLC data.

A more substantial modification replaces the input
string with a tape that can move backward or forward
one position, so instead of outputting a character the
machine writes a new digit at the current position
and then moves the tape either backward or forward one
position.  If we also replace the set {0,1} of two
digits by an arbitrary finite set of `symbols', we have
what is called a `Turing Machine'.


File:	   simplefsm.txt
Author:	   Bob Walton <walton@seas.harvard.edu>
Date:	   Tue Oct  7 00:10:16 EDT 2014

The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.

RCS Info (may not be true date or author):

    $Author: walton $
    $Date: 2014/10/07 04:10:44 $
    $RCSfile: simplefsm.txt,v $
    $Revision: 1.11 $