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.