1
$\begingroup$

Could you give me any tip (not a solution) how to prove that the language of even length words over the alphabet $\{ 0, 1 \}$ such that the number of $1$ in the first half is equal or greater than the number of $1$ in the second half is not context free?

This task can be seen as the next part of the task from: LINK

I tried to use pumping lemma for context free languages but its usage in this case seems to be highly non-trivial for me.

$\endgroup$
1
$\begingroup$

Hint. Once the pumping lemma gives you a pumping length $p$, ask it to slice up the word $\mathtt 0^p\mathtt 1^p\mathtt 0^p\mathtt 1^p$.

For some of the slicings you'll have to pump backwards (that is, from one repetition to none).

$\endgroup$
  • $\begingroup$ Thanks, I've forgotten that you can unpump :) $\endgroup$ – Bartosz Bednarczyk Apr 2 '17 at 14:30

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.