----------------------------------------------------------------
Assignment 2b:  Working with a deterministic FSA

Due: Wednesday 17 September 1997
----------------------------------------------------------------

In this assignment you will be running a LISP program that
can simulate the behavior of a deterministic finite-state
automaton, using the algorithm we discussed in class.
You will also be taking an existing FSA and modifying it.

To begin the assignment, you will need to set things up so
that you can run the LISP program.  Here's what to do:

1.  Create a directory called hw2b in your course account,
    and change directories into that new directory

      % mkdir hw2b
      % cd hw2b

2.  Use the "ftp" program to copy the files you will need.
    Start by calling the ftp program ("file transfer
    protocol") to get to the machine where the files are:

      % ftp umiacs.umd.edu
    
    When it asks you for your login name, use "anonymous":

      Name (umiacs.umd.edu:pr99): anonymous

    When it asks you for a password, it will tell you
    to use your full e-mail address.  Do so
    (e.g. pr99@umd5.umd.edu).

    Now, after a little message, you'll be at the ftp
    prompt.  Tell it to change into the directory where the
    files are:

      ftp> cd pub/resnik/ling645/hw2

    Now you'll tell it to get you all the files there (mget
    stands for "multiple-files get", since you're getting
    more than one file:

      ftp> mget *

    Every time it asks you if you really want to get the
    file, type y for yes and return.

    Now leave the ftp program.

      ftp> quit


3. Now you've got the files you need!  Take a look at file
   fsa-1.lisp.  This is the FSA that we talked about first
   in class.  Notice that what I'm doing here is creating
   a variable called *fsa* and setting it to a list
   containing all the relevant information, as we went over
   in class. (The stars in the variable name are a LISP convention,
   don't worry about it.)

4. Get into lisp, and then load the LISP program:

      (load "fsa")

5. Now load up fsa-1, which will set variable *fsa*
   to that finite state machine.

      (load "fsa-1")

   You can look at the FSA by typing the name of the
   variable:

      *fsa*

   You can also call a function I defined called
   get-initial-state that tells you what the initial state
   of the machine is:

      (get-initial-state)


6. To run the finite-state machine on an input, you call
   the function run-fsa with the list containing the input
   symbols as its argument:

      (run-fsa '(a b a b a))

   Look at the information that was printed out:  it's
   telling you exactly what steps the machine is going 
   through as it reads each symbol of input.  When
   the input was exhausted, the machine wound up in state
   q1, which is a final state, so the value returned by
   the program is the symbol ACCEPT.

7. Play with the program on a few more inputs, e.g.

      (run-fsa '(a b a))
      (run-fsa '(a a b a))

   Get the idea?

8. Ok, let's try a different machine.  Take a look at the
   file fsa-2.lisp.  Notice that the alphabet consists of
   just one symbol.  Load the new FSA, so that it becomes
   the one we're running.

       (load "fsa-2")

   Now run it with a few different inputs:

       (run-fsa '(a a a))
       (run-fsa '(a a a a))
       (run-fsa '(a a a a a))
       (run-fsa '())

   See what language this machine recognizes?

----------------------------------------------------------------
Problem 2b.1 [to turn in]:

  Create a new file, fsa-2even.lisp, containing
  an FSA that works just the same as fsa-2, but
  accepts strings of EVEN numbers of a's, not odd
  numbers of a's.  Then load that file and run it
  on some inputs to make sure it does what you think
  it does.  Turn in:

     "Dribble" output of the program running on the 
     inputs in Step 8, above.
----------------------------------------------------------------

9.  Now we'll do something a little more interesting.
    Load the FSA in "fsa-3.lisp".  This is the finite-state
    machine that we discussed in class, which recognizes
    noun phrases like "the contestant", the "first two
    contestants", etc.  Try running it with a few inputs
    like the following:

      the contestants
      the first two contestants
      the three contestant

    Notice that, correctly, the machine accepts the first
    two inputs and rejects the third.  (By the way, if for
    some reason you don't have a picture of this FSA,
    you can get one at 

     http://umiacs.umd.edu/~resnik/ling645_fa1997/assignments/2/2b_fsa3.ps

10. In the remainder of this assignment, you're going to
    modify fsa-3 to create a new FSA, then modify *that* one
    to create a new one, etc., each time expanding the
    behavior a bit.  The easiest way for you to do this will
    be to go through the following sequence:

      a.  Copy the file with the current FSA to a
          new file, e.g.

             cp fsa3.lisp fsa3a.lisp

      b.  Work out what the new machine should look like
          on paper, working through a few inputs by hand.

      c.  Edit the new file to change the machine specification

      d.  Load the new machine and run it on some inputs

      e.  Go back to step c if the machine doesn't work
          the way it should

      f.  Once the machine does work as it should,
          turn in, for each problem:

             (i)   a graphical picture of the new FSA
             (ii)  a printout of the file containing the new machine
             (iii) "dribble" output showing the machine's
                   behavior on the relevant inputs.

----------------------------------------------------------------  

Problems 2b.2-5 [to turn in]:


Problem 2b.2 

  Notice that the input

    the first contestant

  is not accepted by fsa-3. Create a new machine, let's call
  it fsa-3a, that accepts this input.


Problem 2b.3 

  Modify fsa-3a to create a new machine, fsa-3b, that
  accepts

    the first and second contestants

  but rejects

    the second and contestant


  Remember that the machine has to be deterministic!

Problem 2b.4 

  Modify fsa-3b to create a new machine, fsa-3c, that
  accepts

    the first two contestants admired the second two contestants

Problem 2b.5

  Make sure that fsa-3c REJECTS the sentence

    the contestant admired the contestant admired the contestant

  and if it does not, then create a machine, fsa-3d, from
  fsa-3b, that does reject that input.  (Remember, modify fsa-3b,
  not the fsa-3c that didn't work!)

Problem 2b.6

  Answer:  Why was the solution you adopted in Problem 2b.5
           an inefficient way to represent knowledge about language?
           A hint:  where would you need to make changes in
           order to add "professor" to the FSA as a head
           noun, that is, so that the machine accepted the following?

	     the first professor admired the second contestant
	     the first contestant admired the second professor
  
----------------------------------------------------------------