# Prove or disprove that the following language is context-free

Hi guys I was given this question:

Prove or disprove that the following language is context-free: $$L = \{ \alpha 2 \beta : \alpha,\beta \in 1(0+1)^*, [\alpha]_2 < [\beta]_2 \}$$ where $[x]_2$ is the numerical value of the string $x$ interpreted as a positive number in base 2. For example, $_2 = 8+4+2 = 14$, $_2 = 16 + 4 = 20$, thus $1110210100 \in L$, while $111021110 \notin L$ and $1010021110 \notin L$.

I can't figure out either way if its context free or not. When I was trying to prove it was context free with a DPDA I got stuck because I don't know how to compare two binary strings when one is in reverse of the other because when you put the string left of the 2 into a stack and pull it out it comes out reversed. Because of this I can't compare if one is bigger than the other if they are the same length.

On the other hand I tried using the pumping lemma to prove its not context free. For a string $1^{m}210^{m}$ I can show for two cases when $v^{k}xy^{k}$ is composed of just 1's on the left side or right I can either underpump or overpump. For the third case when $v^{k}xy^{k}$ is composed of the run of 1's on the left and the 0's on the right pumping in either direction doesn't seem to make the left binary number the bigger value.

I am stuck with either direction I have tried so could somebody point me in the right direction?

• IMO it's not easy to prove it with the Pumping Lemma (I'm curious to see if there is a quick solution that uses it). In any case you can prove it using the more powerful Ogden's Lemma (same as Pumping Lemma but with the ability to mark a position that will be pumped) after intersecting $L$ with the regular $L' = \{ 10^*10^*210^*10^*\}$ (if $L$ is CF then $L \cap L'$ is also CF) and using the string $w = 1 0^{a+1} 1 0^b 2 1 0^a 1 0^{b+1} \in L \cap L'$ (marking the rightmost 0s in the second half of the string).
– Vor
Oct 18, 2017 at 9:16
• See our reference question for different techniques.
– Raphael
Oct 18, 2017 at 10:24
• I do not see how the solution by @Vor works. Pumping in the second half of the string just makes the condition "more true". The language looks very non-contextfree. An even trickier case might be the modification where $\beta$ is binary in reverse - this might be linear, if there is a clever way to compare the two numbers. Oct 18, 2017 at 12:15
• @PeterLeupold: you can also pump it zero times (i.e. delete the zeroes). But now I see that the method could not work if the $|v| = |x|$ and $v$ is contained in $0^b$ and $x$ in $0^{b+1}$ ... I'll try to see if there is a fix (and post an answer).
– Vor
Oct 18, 2017 at 14:31
• @Vor Perhaps make $a,b$ larger than the pumping length, so the the segment $vwx$ can only span "neighbouring" segments of $0$'s? Might be similar to $\{ a^mb^na^mb^n \mid m,n\ge 0 \}$. Oct 19, 2017 at 10:30

You can use the pumping lemma in this way.

By closure properties, if $L$ is context free and it is intersected with the regular language $R = \{ 1^* 0^* 2 1^* 0^*$} the resulting langauge $L' = L \cap R$ is still context free.

We can apply the Pumping lemma to $L'$ and prove that it cannot be CF, so $L$ is not CF as well.

Let $p$ be the pumping length; pick

$$z = 1^p \, 0 \, 0^p \; 2 \; 1^{p} \, 1 \, 0 ^p$$

First note that if $vwx$ is entirely contained in the first half, then pumping it one time is enough to make the first half longer than the second half; making $[\alpha]_2 > [\beta]_2$ and pushing the string out of $L$

If $vwx$ is entirely contained in the second half, then pumping it zero times is again enough to make the first half longer than the second half; making $[\alpha]_2 > [\beta]_2$ and pushing the string out of $L$

So $vwx$ crosses the middle of $z$.

At least one, but at most $p$ positions are contained in $vwx$, so $v$ must be in the $0^p$ before the center and $x$ in the $1^p$ after the center.

If $|v| <> |x|$ then - as above - pumping them one (or zero times) would make the first half longer.

But if $|v| = |x| = k \geq 1$ we can still pump it zero times getting the string:

$$z^0 = 1^p \, 0 \, 0^{p-k} \; 2 \; 1^{p-k} \, 1 \, 0^p$$

but

$$[ 1^p \, 0 \, 0^{p-k} ]_2 >= [ 1^{p-k} \, 1 \, 0^p ]_2$$

(for $k=1$ we have $1^p 0 0^{p-1} = 1^{p-1} 1 0^p$)