. 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 aslongas the new first one. This means the second number is greater, and so again the result is not in L1.