. 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 , we have that . This can be shown to be context-free similar to how is context-free.
That L1 is not context-free can be shown using the Pumping Lemma:Note that this version of the lemma guarantees that |vxy| ≤ p.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.
Consider . By the Pumping Lemma, there exists a such that for all k > p, , , and for all . 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 while y is a substring of . 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 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.