Homework 6

CS 3810 – Summer 2008

1. Write a context-free grammar for each set below. (14 points)

   1. {vv^Rww^R | v∈{a,b}*, w∈{a,b}*} [w^R indicates w-reversed]

   2. { a^mb^m+ncⁿ | m,n ≥ 0 }

   3. {a^mbⁿ | 2m = n or m = 2n }

   4. 01{0ⁿ10ⁿ⁺¹1}*

   5. { a^kb^la^mbⁿ | k = m or l = n }

   6. The set of all strings of a's and b's not of the form ww. [Hint: For even-length strings, there have to be two characters that disagree; think about what the rest of the string looks like.]

   7. The set of all strings not in { aⁿbⁿcⁿ | n≥1 }.

2. Exercise 5.1.4 [Right-linear CFG = regular] (4 points)