Due on 07 April 2011, start of class

Please submit a paper copy at the start of class.

CSE 355 Homework Four

Except for the last, a exercises are from Sipser, the course text.
  1. 2.36.
  2. 2.31 and 2.32.
  3. 2.44.
  4. 2.45.
  5. A context-free grammar is in Greibach normal form if every rule has exactly one terminal, followed by zero or more variables, on the right hand side -- except when the variable on the left hand side is the start variable, we also allow a rule with the right hand side being the empty string.

    Show that for every context-free language, there is a context-free grammar in Greibach normal form that generates the language.