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

### 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!!!

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