Hints for HW 4
==============

1) NFA design/subset construction

Give names to the states of your original NFA, then use
these to help keep you organized in parts (b) and (c).

For part (c), you only need to show the states which are
reachable from the start state.

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

2) NFA interpretation/formal definitions

(a) Build up a list of small strings that are/aren't in the language,
then try to generalize.

(b) I.e. present an accepting sequence of states, with the
corresponding sequence of characters and epsilons.

(c) I.e. give the tuple notation corresponding to this diagram.

--------------------------------------------------
3) NFA design with guessing

You can present your design as one big state diagram.  Or you
could use tuple notation.   

My design contained a little group of states that needed to be
repeated at many points in the state diagram.  In such cases, it's
fine to define a symbol for the repeated design element, so you don't
have to keep drawing it many times.

The definition implies that n >= 2.  So your NFA shouldn't accept
any strings of length < 5 characters.

Also, notice that the your NFA must not accept strings of the wrong
format, e.g. aa#b#aa is not in L.

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

4) NFA modification

That is, you are designing a procedure that gets an automaton as
input and produces a modified automaton as output.   Your input
M will be given to you in tuple notation.  You need to write tuple
notation for the output machine N.

We're assuming that M is a DFA, because that simplifies the types
of inputs you need to deal with.   The output will be an NFA, so that
you have access to the full range of NFA features when constructing
your output machine.

Beware:  the transition function for M returns a single state, but
the transition function for N needs to return a set of states.

First figure out how your machine will handle even-length strings.
Then design whatever patch is required to terminate correctly when
the input string has odd length.

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