(30pt) Consider the alphanumeric alphabet = fa; b; : : : ; z; A; B; : : : ; Z; 0; 1; : : : ; 9g and let L be the language of all regular expressions over :
L = fw 2 [ f;; (; ); [; ; g j w is a syntactically legal regular expression over g :
Give an unambiguous context-free grammar that generates L. The grammar should use the following precedence levels, from highest to lowest:
(Kleene star) { highest precedence
(concatenation)
[ (union) { lowest precedence
Show the parse tree that your grammar produces for the string a(a [ b) .
(30pt) For each of the following languages L, prove whether L is regular, context-free but not regular, or not context-free:
L = fxy j x; y 2 fa; bg and jxj = jyjg.
fambn j m; n 0 and m 2ng.
fwRwwR j w 2 fa; b; cg g.
(10pt) Consider the language L = fwwRjw 2 fa; bg g. Below are two proofs, one showing L is context free, the other showing the opposite. Which proof is correct and why?
L is context-free. Here is a context free grammar that generates L:
S ! aA
A ! Sa
S ! bB
B ! Sb
S ! "
L is not context-free. Consider the string wk = akbbak 2 L. Because jwj k, using pumping theorem, wk can be written as wk = uvxyz. Put v = ap; y = aq, where at least one of p and q is not 0. Then, according to the pumping theorem, uv2xy2z 2 L. But uv2xy2z = ak+p+qbbak cannot be written as wwR, for any string w, therefore uv2xy2z 62L, a contradition. This implies that L is not context-free.
(30pt) Show that the following problem is decidable: Given a context-free grammar G, does G generate any odd-length, nonempty strings?
Note Submit your solution as a pdf le on owl.uwo.ca.
1
