COSC 159 - Artificial Intelligence
              Assignment #7

           Morphology with FST's

          Due date: Friday, May 1

GOAL: Write a Finite State Transducer in Lisp (as described in class),
which will correctly process the word list below.  If the transducer
should identify a suffix, the expected output form is listed to the
right of the word.  Your transducer should return the morphological
structure for legal words and should return nil for illegal words.
For example (assuming your function is named morph):

 (morph '(t a s t i n g))

should return

 (t a s t e + i n g)

WORDLIST: Your transducer should recognize and decompose the following words:

 taste
 tasted    (taste+ed)
 tasting   (taste+ing)
 tie
 ties      (tie+s)
 to
 torch
 torches   (torch+s)
 toss
 tosses    (toss+s)
 trap
 traps     (trap+s)
 tries     (try+s)
 try

Your program should not accept (i.e. return nil) illegal words such
as tra, toses, tasti, torche, trie, tast.

METHOD: You should begin by drawing out a transition diagram for the
finite state machine.  Then write a Lisp program to simulate this
machine.  One method of representing a FSM in Lisp can be found in
the file ~mikes/159/fsm.lisp on studsys.  You could modify new_state
so it returns a state and the latest output characters, or you could
update a global output list as you go, but somehow you will need to
construct the output list.
  My program assumes that the input is a list of characters (as in the
example above).  I would suggest that you use this format for your
input and output.

HAND-IN: The transition diagram for your transducer, the Lisp code
implementing this diagram, and a sample run showing that the program
correctly processes the legal and illegal words given above.