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

Bounty: 100

(Practice exam question in computational models)

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

Let $L = {win {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?

Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.