Tutorial sheet for Finite State Automata and Morphology

Exercises

1. Draw the network for all the words given in the example:

   diva, divagate, divalent, divan,
   divaricate, dive, diver, diverge,
   divergent, divers, diverse, diversify

2. Add the facts that correspond to the extra arcs you have added in response to the previous exercise.

3. *How can you use Prolog to check that all the words included in the example are correctly given and no more. (Hint: you do not have to write any extra program code.)

4. *In the demo_fsa/2 program, the second clause of the FSA "machine" is given as:

   % 2 - recursive condition
   demo_fsa([Letter|Letters], State) :-
       arc(State, Letter, Next),
       % next lines are for outputting state details
       write('< '),
       write(State),
       write(' - '),
       write_list([Letter|Letters]),
       write(' >'), nl,
       write('  |'), nl,
       demo_fsa(Letters, Next).
   

   Suppose that the arc/3 sub-goal is moved as shown below:

   % 2 - recursive condition
   demo_fsa([Letter|Letters], State) :-
       % next lines are for outputting state details
       write('< '),
       write(State),
       write(' - '),
       write_list([Letter|Letters]),
       write(' >'), nl,
       write('  |'), nl,
       arc(State, Letter, Next),
       demo_fsa(Letters, Next).
   

   1. Describe how the program now behaves differently from the previous example.
   2. Explain why the program now behaves differently from the previous example. Obviously your explanation should be at a deeper level than merely remarking that the order of sub-goals has been changed. (Hint: this is a question about matching.)

   ---

5. Divide the following words into their morphemes, showing which are the free morphemes, which are the bound morphemes, and which are prefixes and suffixes.
   1. computerize
   2. reorganize
   3. recogniser
   4. uninteresting
   5. computerization
   6. antidisestablishmentarianism

   ---

6. A comparative form of the adjective can be made in English by adding -er to the end of an adjective. For instance, high becomes higher. Form comparative forms of the following adjectives were possible.
   1. taller
   2. small
   3. big
   4. intelligent
   5. beautiful

7. Form the plural of the following nouns by inflection where possible.
   1. boy
   2. toe
   3. potato
   4. foot
   5. woman
   6. child
   7. sheep

8. Give one example of a semi-affix.

   ---

9. Using the FSTN morphological analyser given in the notes, add the following words (including their plural forms where appropriate):
   1. park
   2. telescope
   3. boy
   4. see (including the irregular past tense, "saw")
   5. in - preposition
   6. with - preposition

10. Draw a network diagram for the Finite State Transducer given in the notes for the spelling checker for "train".

11. *What are all the possible mis-spellings that the Finite State Transducer given in the notes for the spelling checker for "train" can correct.