CSE 237, Homework 5, Context-Free languages
Dina Q Goldin, Spring 2006
due 3/01/06 in class

• Please do each problem on a separate page

• Do not turn in those problems (or parts of problems) where we indicate that answers are in the textbook

Problem 1. From a language description to a CFG

(a) Problem 2.4 in the textbook, parts (a), (c), (d), (e). (Note: answers to (a) and (d) are in the textbook)
(b) For each part, also show a parse tree for the string 1010101 in your grammar.

Note: (e) is very similar to an example we did in class, but not quite the same.

Problem 2.8 in the textbook (Note: the answer is in the textbook)

Prove the theorem that the class of RLs is a strict subset of the class of CFLs.
Hints: There are two parts, that every RL is a CFL, and that some CFLs are not RLs. Proof of the first part will proceed by structural induction, very similar to one that for every regular expression, there is an equivalent NFA. As always, you can make use of any result we've already proven in class.

Problem 2.14