In this question, we consider languages over the alphabet {0, 1,#}. If n is a positive integer,

let B(n) be the binary representation of n (with no leading 0’s). For example, B(22) is the

string 10110.

Let L1 = {B(n)#B(m) : n,m 2 Z+ and n > m}. For example, 11000#10110 is in L1

because B(24) = 11000 and B(22) = 10110 and 24 > 22. However, the strings 11000#111111

and 10110#11000 are not in L1. L1 is not regular.

Let L2 = {B(n)#(B(m))R : n,m 2 Z+ and n > m}. For example, 11000#01101 is in

L2 because B(24) = 11000 and (B(22))R = (10110)R = 01101 and 24 > 22. However, the

strings 11000#111111 and 10110#00011 are not in L2.

(a) Is L1 context-free?

(b) Is L2 context-free?

If you answer yes for either language, you must give a context-free grammar for that

language. You do not have to give a formal proof that the grammar generates the language,

but you should give, for each variable in your grammar, a precise description of the set of

strings that the variable generates.

If you answer no for either language, you must give a formal proof that the language is

not context-free.