I have an exam coming up in three days, and there's a thing that I really need to be able to completely understand - that is, of-course, pumping lemmas for CFL. I know how to do prove that a regular language is not regular using PL, but for CFL it's a bit more variables, and I am not entirely sure how to split a string. Below, I will provide with an exercise and my attempt. I want to know, am I doing this correctly and if not, what do I need to do to make it correct? The exercise (although quite similar to the previous question I asked, that question was for regular language and not CFL - in short they are two different questions)

Show, using pumping lemma, that $L2 = ${ $ 0^m 1^k 2^n | n = km $} is not context-free

My attempt goes as following: If L2 is context-free, then there exist a constant $P$ such that $ S \in L2 $ and $|s|\ge P $ which implies that there exist strings uvxyz such that the following are satisfied:

$(1) uv^ixy^iz \in L2 $ for every $ i \ge 0 $

$(2) |vy| > 0 $

$(3) |vxy| \le P$

We must first assume that $L2$ is context-free
$L2$ must have a Pumping length $P$
Must also take strings $0^P 1^P 2^{p^{2}} $ (since n = km)

There are 3 cases

case 1) VXY does not straddle a boundary, belongs to just one So we have $0^P 1^P 2^{P^{2}}$, let's split that into $UVXYZ$,

$U = 0^P$, $ V = 1^r $, $ X = 1^t $, $ Y = 1^{P-r-t}$, $Z= 2^{P^{2}} $
and then we select $i = 2$, which gives us
$uv^2xy^2z = 0^p 1^{2r} 1^t 1^{2p-2r-2t} 2^{p^{2}} = 0^p 1^{2p-t} 2^{p{^2}} \notin L2$

case 2) VXY straddles the first boundary;
like above, we split into $uvxyz$ where
$u = 0^r $
$v = 0^{p-r} 1^t $
$x = 1^r $
$y = 1^{p-t-r} $
$z = 2^{p{2}} $

if we, yet again, select $i = 2$

$uv^2xy^2z = 0^r 0^{2p-2r} 1^{2t} 1^{r} 1^{2p-2t-2r} 2^{p{2}} = 0^{2p-r} 1^{2p-r} 2^{p{2}} \notin L2 $

case 3) vxy straddles the second boundary;
again, like above we split the string into 5 parts $uvxyz$ where
$ u = 0^p $
$ v = 1^t $
$ x = 1^r $
$ y = 1^{p-t-r} 2^t$
$ z = 2^{p{2} - t} $

if we select $i = 2$
we get $uv^2xy^2z = 0^p 1^{2t} 1^r 1^{2p - 2t - 2r} 2^{2t} 2^{p{2}-t} = 0^p 1^{2p-r} 2^{p{2}+t} \notin L2$

Thus we have contradictions for all three cases, which concludes that the language is not context-free!

My general question is am I selecting a string correctly? I.e. does it have to satisfy $|vxy| \le p$ in-order for the $uv^ixy^iz $ where $ i = 2 $ to work? OR must $vxy$ be chosen so that the length is $\le p$? Have I missed cases?

Thank you in advance!

  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Oct 26 '17 at 14:16
  • $\begingroup$ Got it! Thanks. Rephrased the question to make it abide by the community guidelines and to help those who have similar questions. $\endgroup$ – Hoaz Oct 26 '17 at 14:51

Bascially your approach is correct. I have not checked every detail, but have a few remarks:

  • you miss the cases where v or y include a border like v=0011; here pumping destroys the general structure of the word besides the number relations.
  • case 1 would have to be done for the 0s and the 2s, too
| cite | improve this answer | |
  • $\begingroup$ I was under the assumption that vxy was the part of the string to focus on. The first remark is case 2? Also, if the case in which the string straddles no boundary, then showing contradiction for one of elements ( i.e 1 in this case) will automatically prove that the other two contradicts as well? @Peter Leupold $\endgroup$ – Hoaz Oct 26 '17 at 14:55
  • $\begingroup$ Sorry, yes case 2 covers the first remark, but if v=01 (without exponents) then $v²$ is 0101 not 0011. For me it would be fine if you show case 1 only for one of the three possibilities, if you mention that you are aware of the other two cases and understand that they could be treated analogously. $\endgroup$ – Peter Leupold Oct 26 '17 at 16:50
  • $\begingroup$ Yes, v2 would be 0101, which would showcase a contradiction as it's not on the form 0^p 1^p 2^{p2} (0101 breaks this) . I see what you mean, I looked at my second case. It would be (0^p-r 1^t)^2 instead, yes? @Peter Leupold $\endgroup$ – Hoaz Oct 26 '17 at 17:12
  • $\begingroup$ Hmm but then, how would I shorten the string (i.e when I add uv^2xy^2z together)? $\endgroup$ – Hoaz Oct 26 '17 at 17:18
  • $\begingroup$ I am sorry for bombarding you with questions, but another question I have is whether it would be better to just have V and Y taking on ONE element, i.e. perhaps $u = 0^r$ and $v = 0^{p-r}$ x = 1, $y = 1^r$ and then z taking on $1^{p-r-1} 2^{p{2}}$, then when selecting an i, say, 2 - it would not be as hard to simplify. However I still feel that it doesn't cover that case you mentioned just recently. Perhaps the right solution would be to have $0^{p-r} 1^t 0^{p-r} 1^t $ next to each-other, thus showcasing it breaking, instead of dealing with powers. $\endgroup$ – Hoaz Oct 26 '17 at 17:59

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