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.

2. $L_1=\{1u1vw\#1u0v'\mid u,v,v',w\in\{0,1\}^*,|v|=|v'|\}$. That is, both numbers start with 1. Then comes the same (possibly empty) string. Then the first number has 1 while the second number has 0. After that, the first number has at least as many remaining digits as the second one.

Since $L_2=\{u\#v^R\mid u\#v\in L_1\}$, we have that $L_2=\{1u1vw\#v'^R0u^R1\mid u,v,v',w\in\{0,1\}^*,|v|=|v'|\}$. This can be shown to be context-free similar to how $\{u\#u^R\mid u\in\{0,1\}^*\}$ is context-free.

That L1 is not context-free can be shown using the Pumping Lemma:
If a language L is context-free, then there exists some integer p ≥ 1 such that any string s in L with |s| ≥ p (where p is a pumping length) can be written as

s = uvxyz

with substrings u, v, x, y and z, such that |vxy| ≤ p, |vy| ≥ 1, and

u(v^n)x(y^n)z is in L for every integer n ≥ 0.
Note that this version of the lemma guarantees that |vxy| ≤ p.

Consider $\{1^k0^k1\#1^k0^k0\mid k\in\mathbb{Z}^+\}\subset L_1$. By the Pumping Lemma, there exists a $p$ such that for all k > p, $1^k0^k1\#1^k0^k0=uvxyz$, $|vy|\ge1$, $|vxy|\le p$ and $uv^nxy^nz\in L_1$ for all $n\ge0$. One must consider all possible locations of vxy with respect to #. Obviously, v and y cannot contain #. Also, vxy cannot come before #: otherwise, dropping v and y (taking n = 0) will make the number before # have fewer digits than the one after #. Clearly, vxy cannot come after # because v and y can be pumped to make the second number greater that the first.

This leaves the case where # is in x. Since |vxy| <= p and k > p, v is a substring of $0^k1$ while y is a substring of $1^k$. If |v| > |y|, then removing v and y (taking n = 0 above) makes the first number shorter than the second, so the result is not in L1. Therefore, |v| <= |y|. By doubling v and y (taking n = 2), we make the second number start with $1^{k'}$ where k' > k, and the new second number is at least as long as the new first one. This means the second number is greater, and so again the result is not in L1.

3. how is { u # u^r } is context free?

4. It is generated by the following grammar.

S -> #
S -> 1S1
S -> 0S0