CSE 237, Homework 4 (Context Free Grammars)
due 10/4/17 in class


In your proofs, number your steps and justify each one.

Problem 1. From a language description to a CFG

Give context-free grammars generating the following languages over {0,1}:

(a)    {w : w equals the reverse of w, that is, w is a palindrome}

(b)   {w : the length of w is divisible by either 3 or 4}

For part (b), also show the parse trees and the leftmost derivations for the following two strings: 011010 and 0011.

Note: to make sure your grammars are correct, take strings that do or do not belong to the language and see if they can or cannot be generated by the resulting grammar.

Problem 2. From a DFA to a language description

Let CFG G be the following grammar with start variable X:

X -> a X b | b X a | X X | epsilon

a)      Give a simple description of L(G) in English.(Hint: create a bunch of derivations (or parse trees) first to see what you can, and canít, get)

b)      Prove that G is ambiguous.

c)      Find an equivalent grammar thatís not ambiguous.

Problem 3.  Converting REs to CFGs

We showed in class how to construct CFGs for union, star, and concatenation of existing CFLs. We also showed how to construct CFGs corresponding to regular expressions empty-set, epsilon, and c (where c is some member of Sigma).

a)      Use these constructions to create CFG for the following RE.  Do it in steps, building up from the simplest CFGs for the smallest RE subexpressions, and to the final CFG for the whole expression. Don't worry that your grammar is not as simple (small) as can be. Note: don't let your variable names clash along the way!

    ††††††††††††††††††† a ((ba)* U b)

b) Given the existence of these constructions, prove the theorem that all regular languages are context free.

Hint: Proof will proceed by structural induction on regular expressions, very similar to how we proved that for every regular expression, there is an equivalent NFA.