Specifications for FA/FST Programs
  1. Establish a machine's five items and make them a quintuple.
  2. Transition structure and function
    1. User-friendly conventions for list of lists.
    2. Conversion of the transition structure to an array.
    3. Validation of it (each cell should be a state or empty)
    4. An access function for the transition array.
  3. The closure computation (delta-star) for multiple transitions
  4. Recognition: Starting at q0, use delta-star on the input and check for reaching an accepting state.
  5. Input: Allow input of a string or a list of symbols. In lisp, use the (generic) sequence function, ELT
  6. Output: Produce the solution path (states visited), not just accept/reject.
  7. Termination:
    1. by end of input
    2. by empty cell - so trap state is not required
  8. Nondeterministic FAs:
    1. could do subset construction, but instead...
    2. either implement backtracking or
    3. keep track of all possibilities in parallel
  9. DFA and NFA together: delta takes atom or one-element list
  10. Lambda transitions:
    1. add lambda as a special member of the list of input symbols
    2. lambda heads an extra column of delta
    3. closure of lambda requires a function
  11. Transducers:
    1. representation of outputs
    2. adjust delta
    3. compute lambda closures from each state
    4. lambda closure needs to give all possible output sequences for each state reached
  12. Upgrades for compatibility with Jurafsky & Martin text.
    1. Drop "Q" in the transition function; eg, 3 for Q3
    2. Categories of input symbols, eg, VOWEL
    3. Multi-character output on an arc; eg, "^s#"
    4. Output as a string
    5. Default pairs in FSTs: output=input