Hints for Homework 7
====================

(1) Suffix languages are not in Sipser, only in the notes for lecture
10.  First see if there are some states with really simple suffix
languages.   Then try to analyze the states with more interesting
suffix languages.

(2) None of these should be hard.  Remember that matching pairs of
characters should be generated by a single rule application.
E.g. each application of the rule A -> cAd generates one matching pair
of c's and d's.

(3) If you can't immediately see what is going on, try running the
rules to generate some example strings from the language.   Notice
that the start symbol is T, not S.

(4) The actual construction is not difficult.   The hard part of this
question is figuring out what we're asking you to do.

You need to design a general algorithm, which converts an input pattern p
to the corresponding NFA N_p.  Someone (not you) will then run N_p on input
text files.   

If you find it hard to picture the mathematics, you might think of how to
write C or Java code.   Your input p would be in an ASCII file, which you
might read into a 1D array.  Your output N_p would also be in an ASCII file.
This might contain a list of alphabet symbols, a list of states, then a
list of transitions (input-state,char,output-state), then the start and
final states.   

You can design your NFA N_p using one state for each position in the
pattern string, plus perhaps an extra start or final state.  The
transitions to/from each state are then closely related to what is
in the corresponding pattern positions.

Allowing the []* constructions to nest only APPEARS to add complexity.
It should not make much difference to your NFA construction.