1
$\begingroup$

How can we prove that:

$$ L = \{ w_1\#w_2 \mid w_1 \in w_2;\; |w_2| > |w_1|;\; w_1 , w_2 \in \{0, 1\}^*\} $$

is not context-free?

The language defines $w_1$ as a sub-string of $w_2$, and they are separated by a $\#$. This is easy with the CFG pumping-lemma for a slightly different language with $|w_2| \ge |w_1|$ by using the special case of $|w_2| = |w_1|$ (i.e. $w_1 = w_2$).

But here, $w_1$ is a proper sub-string of $w_2$ so I can't do the same. I fail to push the string out since we can always pump, for example the first symbol of $w_2$.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Some questions can't be shown to be non-context-free by the Pumping lemma; I recommend you check out our reference questions for more methods. $\endgroup$ – Raphael♦ Apr 25 '14 at 12:39
  • $\begingroup$ The $|w_2| \ge |w_1|$ is easy, $|w_2| > |w_1|$ is hard. So this site should not have any pumping-lemma applications in the future just because of that duplicate question? $\endgroup$ – perreal Apr 25 '14 at 12:46
  • $\begingroup$ Okay, now I understand the question; thanks for clarifying. It probably is still a duplicate (I'd imagine Ogden's lemma might work, but I did not try it out) and you don't really display your attempt (cf here). You do note why the Pumping lemma fails, though, so I'm giving you the benefit of the doubt and reopen. $\endgroup$ – Raphael♦ Apr 25 '14 at 12:56
  • $\begingroup$ Thanks, are you aware of any theorems saying the pumped string should contain all distinct symbols in a sub-string with some sufficient length? $\endgroup$ – perreal Apr 25 '14 at 13:05
  • $\begingroup$ @perreal There is no such theorem since it's not true. Consider for example the language $a^*$. $\endgroup$ – Yuval Filmus Apr 25 '14 at 13:58
1
$\begingroup$

For large enough $p$, consider the word $w = 0^{p+1}1^{p+1}\#0^{p+1}1^{p+2} \in L$. Mark the part $1^{p+1}\#0^{p+1}$. According to Ogden's lemma, we can write $w = uxyzv$ such that $xyz$ contains at least $1$ and at most $p$ marked symbols, and $ux^iyz^iv \in L$ for all $i \geq 0$. The pumped part $xyz$ cannot lie all to the right of $\#$ since then pumping it down would result in a word not in the language (here we crucially use the fact that only the $0^{p+1}$ part to the right of $\#$ is marked). It also cannot lie all to the left of $\#$ since then pumping it up would result in a word not in the language. It follows that the part of $xyz$ to the right of $\#$ is of the form $0^k$, and the part of $xyz$ to the left of $\#$ is of the form $1^\ell$ (otherwise, there would be more than $p$ marked symbols). However, pumping up, the resulting word is not in the language. This contradiction shows that $L$ is not context-free.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Can we not use the same logic to prove $0^n1^n$ is not CFG by marking 0's? Sorry if this sounds dumb. $\endgroup$ – perreal Apr 25 '14 at 16:19
  • $\begingroup$ Hopefully not. Try it out to see what goes wrong. Check out the statement of Ogden's lemma first. $\endgroup$ – Yuval Filmus Apr 25 '14 at 17:34
  • $\begingroup$ I think what goes wrong with $0^n1^n$ is, we have to show for all possible markings to show non-cfl. I also think since you are just showing a single possible marking in the proof it is not complete. So perhaps this language obeys the lemma's. $\endgroup$ – perreal Apr 27 '14 at 7:27
  • $\begingroup$ @perreal Ogden's lemma states that there exists $p$ such that for every word in $L$ and every possible marking with at least $p$ marks, there is a way to break the word in a certain way and pump it in a certain way. We get to chose the marks. Otherwise Ogden's lemma doesn't give us anything beyond the usual pumping lemma. $\endgroup$ – Yuval Filmus Apr 27 '14 at 16:21

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.