Hints for HW 8
==============

1) This is not complicated.  When you have a component that
can be repeated, be clear on whether it has to occur at least
once or can be omitted entirely (x* vs. x+).

2) This problem is largely mechanical.   Be clear on the difference
between a parse tree and a derivation.

The problem will be easier to do if you first figure out what the
grammar does.  Start with the variables at the bottom of the tree: T
for grammar (a), B and C for grammar (b).   What can each of these
variables generate?

3) When you handle the case where i is not equal to j, check that
your machine does the right thing both when i > j and when j > i.

Keep your PDA well-structured.   E.g. make sure each state has a
clear purpose, divide into independent branches if you have an OR
of two possibilities.   This is MUCH more important than using
the minimum number of states/transitions.  The graders will take
off points if the PDA is too hard to understand.

Avoid having two (or more) states that are connected in both directions
with epsilon transitions.   In previous terms, this has been a big
feature of complex and hard-to-grade PDAs.

4) (b) First, figure out how to generate the four characters involved in
the swap.  Then add grammar rules to add matching pairs of characters
in all the places they can occur:   outside the swapped chars,
inside the swapped chars, and between the two chars involved in the
swap.

(c) Your grammar from (b) will generate the pair wi,wj.   Build 
a junk generator which will generate a list of zero or more strings with
any contents, separated by #'s.   

When you think you are all done, check that you are generating # in
exactly the right places.  Check special cases such as when i and j
are adjacent positions, or one of them is at the start or end of the
sequence.

(5) Write out some small parse trees (or derivations) using the
grammar, to generate a small set of concrete examples.  Try applying
the rules in different orders, until you find an answer to (a).  A
good set of examples should give you some ideas for what's happening
in (b).