I have started pumping lemma for context-free grammar by reading Sipser's book and there are two questions right at the end end of the topic which I don't understand how to solve or where to start from?

I have to show that the following languages are not context-free

L = { w | w = 0a 1 b 2 ab where a, b are >= 1 }

and another question that goes like this:

L = { w | w = x11x21...1xk where k >=0 and each xi is ∈ {0}*, and xi ≠ xj whenever i ≠ j

How would I tackle this problem? I understand pumping lemma in general but for these questions I can't seem to apply it.

  • $\begingroup$ I looked at that example before posting this question. That example just generalizes the idea of pumping lemma but the questions that I have are special cases. @fade2black $\endgroup$
    – Saad
    Dec 9 '17 at 4:36
  • 1
    $\begingroup$ What is your particular question? You are asking "How would I tackle this problem?". The answers are in that post. Also, the usual rule is one question per post. $\endgroup$
    – fade2black
    Dec 9 '17 at 4:42

First language: $0^{p}1^{p}2^{p^2}$ - If we make $0$ or $1$ longer, $2$ must get longer too to satisfy the condition of the language. Because of $|vwx|\le p$ $v$ cannot contain $0$ when $x$ contains $2$. Also if either $v$ or $x$ contained two different symbols, we know that it would break the language (there would be a sequence of e.g. $0^{i}1^{k}2^{l}1^{m}2^{n}$ with $l,m > 0$).
The last possibility is when $v$ is of form $1^k$ and $x$ of form $2^{l}$. We will prove by contradiction that this is impossible too. We would need such $k, l>0$ that the next equation holds for all $i \ge 0$ $$p(p+i\cdot k) = p^{2}\cdot i \cdot l \\ p^{2} + p\cdot i \cdot k = p^2 \cdot i \cdot l \\ l = \frac { p^2 + p \cdot i \cdot k }{p^2 \cdot i} \\ l = \frac {1}{i} + \frac {k}{p} $$ From $|vwx|\le p$ and $k,l>0$ we know that $k<p$. Similary $\frac{k}{p}<1$ and $\frac{1}{i} < 1$ for $i > 1$. From those and the fact that $l$ is natural number, the only possible value of $l$ is $1$. That would mean $$p^{2} + p\cdot i \cdot k = p^2 \cdot i \\ k = \frac{p \cdot i - p}{i} \\ k = p - \frac{p}{i}$$

There are two problems with this: first it would hold only when $i$ divides $p$ and $k$ would be dependant on $i$ but has to be a constant. Thus we have proved this is impossible too and the lemma is complete.

For the second language, I believe it is pretty difficult example I and I would advise you to first try some easier languages, if you have just started using the lemma.

You can chose for any $p$ a string $0^{0}10^{1}10^{2}1...10^{p-1}10^{p}$ and then you have to enumerate all the possibilities and prove they don't hold for some $i$.

  • Either $x$ or $v$ contains two (or more) $1$'s - then it also contains $10^m1$ so with $i>1$ the pumped string will contain two $x_m$'s so it will not be from $L$.
  • Both $x$ and $v$ contain no $1$'s - with $i=0$ the substrings $x_m$ and $x_n$ containing $x$ and $v$ respectively will get shorter. Since the original string $s$ contained all shorter strings $x_k$ at least one of them will colide with some shorter string.
  • Either $x$ or $v$ contain only $1$. - If that substring is pumped, the new string will contain $...11... = ...1x_{0}1...$, but the original string started with $1... = x_{0}1...$, thus we have a collision.
  • Either $x$ or $v$ are of form $0^{n}10^{m}$ with either $n$ or $m$ greater than $0$. With $i=3$ we get $...0^{n}10^{n+m}10^{n+m}10^{m}...$ where we immediately see a collision.

I hope I did not forget some special case.

  • $\begingroup$ The first questions is not CFL. Test it out with 0^3 1^3 2^9 $\endgroup$
    – Saad
    Dec 9 '17 at 21:52
  • $\begingroup$ @Saad My bad, I for some reason misread it as $0^{a}1^{b}2{a+b}$. I hope I fixed it $\endgroup$
    – Ordoshsen
    Dec 10 '17 at 15:10
  • $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$
    – Raphael
    Dec 10 '17 at 17:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.