**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.