Write a context-free grammar for each set below. (14 points)
{vvRwwR | v∈{a,b}*, w∈{a,b}*} [wR indicates w-reversed]
{ ambm+ncn | m,n ≥ 0 }
{ambn | 2m = n or m = 2n }
01{0n10n+11}*
{ akblambn | k = m or l = n }
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.]
The set of all strings not in { anbncn | n≥1 }.
Exercise 5.1.4 [Right-linear CFG = regular] (4 points)