Hints for HW 9
==============


1. Chomsky-normal form

   Follow the algorithm from lecture 15.  In part (a), remember that
   you need to add a new start symbol before removing the nullable
   variables, to handle the possibility that the start symbol may be
   nullable.

================================================================

2. See the example in Lecture 15.   These proofs are just like
the ones you did earlier for regular languages, except that
you  don't have as many closure properties.  (E.g. context-free
languages aren't closed under intersection.)

You will need to use a proof by contradiction.

Be very careful to apply closure properties only in the proper
direction:  if the input sets are context-free, the output of
the operation must be context-free.

================================================================

3. Grammar-based induction

  See lectures 14 and 15 for examples of induction on derivation length.

  It's ok to assume that the derivations are all leftmost, but state
  explicitly that you are doing so.

  You must use strong induction.  That is, your induction hypothesis
  should state that the claim (version 2) is true for all strings
  which have a derivation of length <= k (not just == k).

  In the inductive step, break off the FIRST step in the derivation.
  Do not attempt to do this proof by taking off the last step in the
  derivation.

  Definitely do not attempt to do this proof by weak induction on the
  lengths of the strings.  Notice that the odd-length strings are
  generated by one part of the grammar, and the even-length strings by
  another part of the grammar.  So the derivations for strings of
  length k+1 are only distantly related to the derivations for the
  strings of length k.

================================================================

4. PDA to CFG conversion

(a) Remember that you are looking for a pair of transitions, one
of which pushes a symbol t onto the stack and the other of which
pops the same symbol t.


================================================================
5. Old Time PDA

There's a lot of text to read through here, but the problem is not
actually all that complicated.  Your answers to (a) and (b) should be
short.  "Explain clearly" means describe the key reason why (a) is
true, and the key ideas behind any constructions involved, without
writing out all the details of the tuple notation.

Part (c) is for people that know no fear in handling formal notations
and lions, and want to flesh out some or all of the details of the
tuple notation.

================================================================