Chapter 15
1ii and 2
It's a lot of work to draw these things, and I don't think I should have to, because I've already done it for one grammar.   Look at your notes for chapter 15, page 7.  ALL PDA's for ALL CFG's follow this pattern.  It's like using a subroutine where all you have to do is supply the right parameters.  But first read the opening lecture material for the chapter; pages 1-6.

Now look at page 7.  Run a sentence from the grammar (e.g. "cdd") on the PDA shown, to help you understand how it works.  You will have to keep track of multiple (pushdown stack, input string) pairs as shown on pp. 3 and 4, because the PDA is non-deterministic.

Now note the following about p. 7:
(1)  The CFG starts with a START state and a Push of the sentence symbol.  This is standard.
(2)  The Push transitions to a Pop state.  This is standard.
(3)  The Pop state has a transition for each terminal of the grammar, which will be a Read of that terminal, and then goes to the Pop state.  This is standard.
(4)  The Pop state has a transition for each grammar rule, transitioning on the LHS of the rule to a series of Push states that pushes the RHS symbols in reverse order and then goes to the Pop state.  This is standard.
(5)   The Pop state has a D-transition to a Read state which reads a D and Accepts.  This is standard.

That's all there is to it!

7ii
Consider all posible derivations that derive 4 a's:
S Þ (S)(S) Þ ((S)(S))(S) Þ (((S)(S))(S))(S) expanding the first S, or
                                           ((S)((S)(S)))(S) expanding the second S, or
                                           ((S)(S))((S)(S)) expanding the third S
using now S ® a, we get 3 different derivations
Now we do
S Þ (S)(S) Þ (S)((S)(S)) Þ  ((S)(S))((S)(S)) expanding the first S (same as third above)
                                            (S)(((S)(S))(S)) expanding the second S, or
                                            (S)((S)((S)(S))) expanding the third S
This adds 2 more for a total of 5.

13i
a(a+b)*
all it does is (1) read the first character and reject if not an "a"  (2) otherwise immediately push baa and then just pop them and accept.  What's left of the input is ignored -- it can be anything.

15i
S ® XB | AB
X ® AS
A ® a
B ® b

15ii  see above

Chapter 16
2ii
Can't use productions:
S ® AX (because then you would have to use X ® SA, which self-embeds S)
S ® BY (because then you would have to use Y ® SB, which self-embeds S)
X ® SA and Y ® SB now become useless, leaving us with
S ® AA | BB, A ® a, B ® b
only two derivations possible.  You make the trees.

4i
Nullables = {A}
Productions after removing l-productions: S ® AbA | bA | Ab | b, A ® Aa | a

4ii
Chomsky-ize:  S ® AX | BA | AB | b, X ® BA, A ® AY | a, Y ® a, B ® b

4iii
going back to original grammar - can't use A ® Aa, so left with
S ® AbA, A ®l
Only 1 derivation possible.  You make the tree.

9 (no question of this type on exam, and I'm getting tired)

13
CFG that genarates it:  S ® aSbC | abC, C ® Cc | c

15
An even palindrome is of the form xreverse(x), where x is an arbitrary string

Note:  reverse(xy) = reverse(y)reverse(x), so reverse(x²) = (reverse(x))²
and reverse(xⁿ) = (reverse(x))ⁿ

Now we attempt to use the Pumping Theorem:
We have to show that, no matter how we break up a palindrome into uvwxy, uvⁿwxⁿy will not be a PAL for some n.

But, any sufficiently long palindrome can be broken up into the five parts uvwxy as follows:

lTⁿ(any middle of the palindrome)(reverse(T))ⁿl = Tⁿ(any middle of the palindrome)(reverse(Tⁿ))
by the above note.  This is still a PAL!  No contradiction! Can't use Pumping Theorem!