# Pumping lemma for context-free languages - Am I doing it right? [closed]

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?

## closed as unclear what you're asking by David Richerby, Evil, fade2black, Juho, Kyle JonesNov 15 '17 at 1:17

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• 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. – David Richerby Oct 26 '17 at 14:16
• Got it! Thanks. Rephrased the question to make it abide by the community guidelines and to help those who have similar questions. – Hoaz Oct 26 '17 at 14:51

• 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. – Peter Leupold Oct 26 '17 at 16:50
• 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. – Hoaz Oct 26 '17 at 17:59