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

(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?

• Every word can be trivially pumped using pumping lemma for CFL. Just set v the first half of the word, and x the second half of the word. However this is not sufficient to claim it is CFL. – Marcelo Fornet Jun 20 '20 at 21:39
• @MarceloFornet While your sentiment is shared, the length of $vx$ is greater than any fixed pumping length most of the time. A stronger claim would be that $L$ satisfies the pumping lemma. – John L. Jun 20 '20 at 22:34
• @JohnL.Thanks for pointing out. Also was thinking the problem with the first half balanced. – Marcelo Fornet Jun 20 '20 at 23:07
• Here is a possible approach. Try proving the following more general conjecture. Given a context-free language $H$, let $D=\{fb: f\in H, b\in\Sigma^*, |f|=|b|\}$. If $D$ is context-free, then $D$ is regular. – John L. Jun 22 '20 at 1:25
• @JohnL. interesting idea, I’ll give it a shot. Tomorrow the TA for the course is holding a virtual office hour, too. I’ll ask her then and update here if she happens to have a solution. – Or Bairey-Sehayek Jun 22 '20 at 22:53

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

1. $$(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''$$

1. 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''$$