0
$\begingroup$

I am studying Pumping Lemma for Context Free Languages, wherein, I am slightly confused in a question where one of the case doesnt obey all rules but another case does. What's the conclusion? Do we call it a contradiction and declare the language is not context free or do we say there is no contradiction?

If its the former, it will declare (a)^n(b)^n as non-context free using Pumping Lemma even though we know its a context free language, since some of the cases will not obey the 3 conditions at the same time.

Edit:

By cases, I mean v and y's existence in different parts of the string. In a string aaaaabbbbb, either v or y could fully be in a, partially be in a and b or fully be in b. ( Assuming you break the string into S = uvxyz where v and y are the repeating pieces)

$\endgroup$
2
  • $\begingroup$ Could you clarify what you mean by "cases"? Perhaps give an example of an application of the lemma where you have this confusion. $\endgroup$
    – Shaull
    Sep 13, 2020 at 9:45
  • $\begingroup$ Edited the question. $\endgroup$
    – ChaoS Adm
    Sep 13, 2020 at 9:47

1 Answer 1

1
$\begingroup$

This is a common question regarding pumping lemmas, and it is completely answered by carefully understanding the quantifiers in the lemma.

The lemma itself says the following:

For every CFL $L$, there exists a constant $p$ such that for every word $w\in L$, if $|w|>p$, then there exist words $u,v,x,y,z$ such that $w=uvxyz$, and (1) $|vxy|\le p$, (2) $|vy|\ge 1$, (3) for every $i\ge 0$, $uv^ixy^iz\in L$.

Now, the typical usage of the lemma is by contradiction, so we have a language $L$ which we suspect to be not a CFL, and we show the negation of the lemma (read this carefully, and see how we negate the formulation of the lemma):

For every constant $p$, there exists a word $w\in L$ with $|w|>p$, such that for every decomposition $w=uvxyz$, if (1) and (2) hold, then there exists $i\ge 0$ such that $uv^ixy^iz\notin L$.

As you can see, in order to apply the lemma, we can choose the word $w$, but we are given $u,v,x,y,z$. Then, we assume that cases (1) and (2) hold, and deduce that (3) doesn't hold. It is really important to understand which elements we can choose, and which we need to be given without choice. These correspond to existential/universal quantification.

$\endgroup$
8
  • $\begingroup$ If we are able to deduce in any one of the cases that (3) holds even though the other cases deduce that (3) doesn't hold, do we say it's a context free language since one of the cases was able to hold all 3 cases at the same time? $\endgroup$
    – ChaoS Adm
    Sep 13, 2020 at 11:16
  • $\begingroup$ I don't understand your question. If assuming (1)+(2) implies that (3) doesn't hold, then the language is not CFL. $\endgroup$
    – Shaull
    Sep 13, 2020 at 11:37
  • $\begingroup$ I am terrible at explaining apparently. Um let's take it with an example. Take a^5b^5 . If I was to take the length of v and y same ( lets say u = aaaa, v= a, x = b, y = b, z = bbbb) , it satisfies (1) and (2) and also satisfies (3) . However, if I take them to be different length ( u = aaaa, v = a, x = b, y = bb, z = bbb ) , (1) and (2) still hold but (3) doesnt. What's the conclusion? $\endgroup$
    – ChaoS Adm
    Sep 13, 2020 at 11:40
  • $\begingroup$ That's exactly what I meant in the last sentence of my answer: you cannot choose u,v,x,y,z. They are given to you (i.e., you need to prove something about any such choice of uvxyz). What you can do, is assume that (1) and (2) hold, in order to contradict (3). So what you ask doesn't apply, as you can't choose them. $\endgroup$
    – Shaull
    Sep 13, 2020 at 11:42
  • $\begingroup$ I am confused. If there's a fixed u,v,x,y,z for a string w, how do we know what they are? Both the ones I took obey rules (1) and (2) for picking them and are not arbitrarily taken from the string. $\endgroup$
    – ChaoS Adm
    Sep 13, 2020 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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