5
$\begingroup$

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, $[1110]_2 = 8+4+2 = 14$, $[10100]_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?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Vor Oct 18 '17 at 9:16
  • $\begingroup$ See our reference question for different techniques. $\endgroup$ – Raphael Oct 18 '17 at 10:24
  • $\begingroup$ 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. $\endgroup$ – Peter Leupold Oct 18 '17 at 12:15
  • $\begingroup$ @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). $\endgroup$ – Vor Oct 18 '17 at 14:31
  • $\begingroup$ @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 \}$. $\endgroup$ – Hendrik Jan Oct 19 '17 at 10:30
2
$\begingroup$

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$)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.