CIS 420/520 Assignment 4
Context Free Grammars
The problems here are all from the second edition of the Sipser book. If you
are using the first edition, many of the problems are the same, but the numbering
of the problems is not.
Assignments are due at the beginning of class on the due date indicated.
Use machine copy if at all possible - in any case, writing and diagrams
must be neat and legible.
Assignment 4 is due Monday, November 5.
Sipser 2.4c
Give a context-free grammar that generates the following language, where
the alphabet Σ is {0,1}.
{ w | the length of w is odd }
Sipser 2.6b
Give a context-free grammar to generate the complement of the language
{ anbn | n ≥ 0 }
Sipser 2.16
Show that the class of context-free languages is closed under the regular
operations: union, concatenation, and star.
Sipser 2.26
Show that if G is a CFG in Chomsky normal form, then for any string
w ∈ L(G) of length n ≥ 1,
exactly 2n - 1 steps are required for any derivation of w.
Sipser 2.19 (for CIS 520 students)
Let CFG G be
S → aSb | bY | Ya
Y → bY | aY | ε
Give a simple description of L(G) in English.
Use that description to give a CFG for the complement of L(G).