Is the language of words that are unbalanced in the first half context-free?

Question

(Practice exam question in computational models)

Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s.

Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and the first half of $w$ is unbalanced$\}$. Determine whether or not $L$ is context-free and prove your answer. You may do so by drawing an NPDA which recognizes $L$, using the closure properties of CFLs, or the relevant pumping lemma.

This question has been bugging me for a while; my gut tells me it isn't context-free since any PDA that recognizes it would have to check the balance of the string read thus far while simultaneously measuring its length and non-deterministically choosing an unbalanced point to validate as the middle of the word. I also haven't been able to express it as a union or concatenation of two CFLs or find a CFG which generates it.

On the other hand, I haven't been able to either find a word in the language that can't be pumped or prove that every word can be pumped.

Does anyone have any ideas on how to proceed?

Answer 1

Perhaps it can be proved using Ogden's Lemma and its generalization by Bader and Moura, this is a rather informal sketch of the proof.

First restrict $L$ to strings of length $4n$ and apply to it the following homomorphism between $\Sigma = \{ 0,1 \}$ and $\Sigma' = \{ a, b, c\}$:

$h(11) \to a$
$h(00) \to b$
$h(01) \to c$
$h(10) \to c$

If $L$ is CF then also the new language $L'$ obtained is CF by closure properties.

Informally $L'$ contains an unbalanced number of $a$ and $b$ in the first half and the number/occurences of $c$ doesn't matter.

Further restrict $L'$ by intersecting it with the regular language $R = \{ a^* (c^* b^*)^* \}$; let $L'' = R \cap L'$

For example the string

$a a c b | cccc \in L''$ corresponds to $11\;11\;10\;00\; |\; 10\;10\;10\;10 \in L$ ($|$ is used to mark the half of the string for better readability)

$a b c c | cccc \notin L''$ corresponds to $11\;00\;10\;10\;|\;10\;10\;10\;10 \notin L$

Suppose that $L''$ is CF, and $p$ is its pumping length. Build $w \in L''$ concatenating these four parts:

1. $(\;a^p\;)$ leading $a$'s

2. $(\;c^j\;)$ a sequence of $c$s, we'll fix $j$ below

3. $(\;c^{p} \;b\;)$ repeated $p + p!$

If $n$ is the constant of the Bader-Moura's condition, then we pick $j$ large enough to exclude all the symbols in part 1 and 3: $j \geq n^{p+(p+1)(p+p!)+1}$

4. $(c^k)$ where $k$ is large enough to be pumped exluding all previous symbols: $k \geq n^{p + j + (p+1)(p+p!)+1}$

$w = a^{p} \; c^j \; (c^{p} \;b )^{p+p!} \; c^{k} $

Now we mark the first $a$ sequence as distinguished, the string $vx$ must contain $0 < q \leq p$ distinguished positions ($\#a_{vx} = q$) by Ogden's lemma; $vx$ can also contain one $b$ (not more than one because the $b$s are spaced with more than $p$ symbols $c$) and $0 \leq r < p$ symbols $c$ ($\#c_{vx} = r$).

1. if $vx$ is such that $\#a_{vx}=q$, $\#b_{vx}=0$, $\#c_{vx}=r$:

then we can pump $i = p! / q $ times and we obtain the same number of $a$s and $b$s; if after the pump some $b$s fall after the half of the string, we can pump the final $c^k$ independently from the rest of the string and we can "push" all $a$s and $b$s back in the first half (and $\#a_{w'} = \#b_{w'} = p + p!$), so the pumped string $w'$ is not in $L''$

2. if $vx$ is such that $\#a_{vx}=q$, $\#b_{vx}=1$, $\#c_{vx}=r$:

then each time we pump we increase the number of $a$s and $b$s, but we cannot guarantee that we reach the same number (e.g. in the case $\#a_{vx}=q=1\#b_{vx}$). But in this case the derivation tree "isolate" the $c^j$ part of the string from the final part $c^k$, so we can pump them independently.

We can pump $c^j$ as many time as needed to "push" $p!$ symbols $b$s to the second half of the string. Suppose that the pumping length of $c^j$ is $s$ (that must be even), the half of the string is shifted towards the $b$s by $s/2$. We have $s \leq p$ so after each pump at most one $b$ is "pushed" to the second half, because the "distance" between $b$s is $p$. So also in this case we get a string $w'$ not in $L''$