0
$\begingroup$

Say I need to prove that

$L=${$a^n b^n c^n; n\geq 1$} is not context free language

I take n=3. w=aaabbbccc

Here |w|=9.

we know by pumping lemma-:

|vxy| $\leq$n so vxy=abb

|vy| $\geq$1 so vy=ab

Hence I suppose-: u=aa v=a x=b y=b z=bccc

So

$u v^i x y^i z$ =aaaabbbbccc

Hence it is not in L so L is not regular.

But this looks funny to me to be approved in exam. Will it be approved in exam in your opinion? I know it is broad question but there must be CS teachers in cs.stackexchange to know about this? The other proof of this is too hard for me to understand. So I have resorted to this.

$\endgroup$
10
  • $\begingroup$ Im not a teacher, but the proof is missing the pumping length. In addition, you cant conclude that $vxy=abb$, since you dont know what $u$ and $z$ are. For the same reason, you dont know what $vy$ is. So I wouldn't approve this proof in an exam. $\endgroup$
    – nir shahar
    Nov 11, 2021 at 13:54
  • $\begingroup$ I took the pumping length i=2 p robably. $\endgroup$
    – supcem
    Nov 11, 2021 at 16:51
  • $\begingroup$ You cannot choose the pumping length. $\endgroup$
    – nir shahar
    Nov 11, 2021 at 16:58
  • 1
    $\begingroup$ I don't think this guy chooses what the pumping constant is. I see that for every language he wants to disprove using the pumping lemma, he starts with "Exists p pumping constant" in pink. $\endgroup$
    – nir shahar
    Nov 11, 2021 at 17:22
  • 1
    $\begingroup$ @supcem he is in fact wrong. Even if its a youtube video, it doesn't automatically imply that he is correct. In the video, he chose the pumping constant to be $6$ - which is not correct. If you could choose the pumping constant, then you could disprove the regularity of $\{1\}\cup \{0\}^*$, which is clearly regular. $\endgroup$
    – nir shahar
    Nov 12, 2021 at 9:36

2 Answers 2

1
$\begingroup$

That's an incorrect proof. There are two reasons.

You say that you need to prove that $L$ is a context-free language. The pumping lemma cannot help you with that, since it can only be used to prove that $L$ is not regular (which doesn't imply that $L$ is context free) or that $L$ is not context-free (in its variant for context-free languages).

Assuming instead that you wanted to prove that $L$ is not a regular language, it is not correct to just pick "an example" word.

The pumping lemma statement is as follows:

Pumping lemma: if $L$ is regular, then there exists some positive integer $p$, such that for every word $w$ with $|w|\ge p$, there exists a way to write $w$ as $xyz$ with $|xy| \le p$ and $y \ge 1$, such that for every integer $i \ge 0$, $xy^iz \in L$.

If you want to show that $L$ is not regular, then you need to prove that the pumping lemma does not hold for $L$. In other words you need to show that the following holds:

Negation of Pumping Lemma: for all positive integers $p$, there exists a word $w$ with $|w|\ge p$ such that, for every possible choice of $x,y,z$ with $w=xyz$, $|xy| \le p$, and $|y| \ge 1$, there exists an integer $i \ge 0$, such that $xy^iz \not\in L$.

This means that you cannot choose a fixed length of $|w|$. Moreover, you cannot choose the decomposition of $w$ into $x$, $y$, and $z$, but you need to consider all possible decompositions (that satisfy the constraints of the statement above).

Here is a proof that your specific $L$ is not regular by showing that "Negation of Pumping Lemma" holds.

Given any value of $p$ (recall that our proof must hold for all $p > 0$), we choose $w=a^p b^p c^p$ and we notice that $|w| = 3p \ge p$. We are allowed choose $w$ since we only need to show that a suitable word $w$ exists.

We now consider all possible ways of writing $w$ as $xyz$ with $|xy|\le p$ and $|y| \ge 1$. Notice that $xy$ must contains only $a$s, therefore $x$ must be of the form $a^j$ for some $j \ge 0$, $y$ must be of the form $a^h$ for some $h \ge 1$, $j+h \le p$, and $z$ is of the form $a^{p-j-h}b^p c^p$.

Next, we pick a value for $i$ (a single value suffices since we only need to show that a suitable value exists). In particular we choose $i=0$.

We need to verify that $x y^i z \not\in L$. This is true since: $$ x y^i z = a^j (a^h)^i a^{p-j-h}b^p c^p = a^{p-h}b^p c^p, $$ and $h \ge 1$.

This shows that "Negation of Pumping Lemma" holds for $L$, i.e., that the Pumping Lemma fails for $L$. As a consequence $L$ cannot be regular. This concludes the proof.

$\endgroup$
5
  • $\begingroup$ this is for context free language. i rewrote the question. it is bit tougher to solve like that in case of context free language so I resorted to that way. Is there some simpler way of this proof in CFL? I can do proofs for RL I used easy theory youtube channel explanations for that. But his explanations for CFL aren't easy to follow. $\endgroup$
    – supcem
    Nov 11, 2021 at 15:36
  • $\begingroup$ can you share some resources for me to get through pumping lemma proofs, it seems very confusing to me. any easy proofs techniques. i loved easy theory videos of pumping lemma for regular language. but his videos for cfl aren't my cup of tea. any resources please recommend. $\endgroup$
    – supcem
    Nov 11, 2021 at 15:39
  • $\begingroup$ You could have a look at chapters 4 (for regular languages) and 7 (for context-free languages) of the book "Introduction to Automata Theory, Languages, and Computation" by Hopcroft et al. $\endgroup$
    – Steven
    Nov 11, 2021 at 17:02
  • $\begingroup$ youtube.com/watch?v=9R-vRroo_dE&t=2s this is what I am talking about, is this correct? There is a youtube video, so it can't be wrong I mean he must have seen this somewhere to teach like this. Isn't it?? $\endgroup$
    – supcem
    Nov 12, 2021 at 5:25
  • $\begingroup$ The youtube video is wrong. Specifically, it is wrong at minute 6 when they pick $c=6$. Unfortunately (?), the fact that something is an a youtube video doesn't mean that it must be right... $\endgroup$
    – Steven
    Nov 12, 2021 at 13:16
1
$\begingroup$

There are very many flaws in this proof attempt, and I would not give marks for this.

First of all: $L$ is NOT context-free and the pumping lemma for context-free languages can only be used to prove that a language is NOT context-free. Similar to the better-known pumping lemma for regular languages, there are non-context free languages that have the pumping properties required by the lemma.

Second: the pumping properties rely on the assumption that there exists a finite pumping length $p$, and that only strings containing $p$ or more symbols are subject to the requirements of the lemma. Therefore, you can't use the string $aaabbbccc$, because it's possible $p > 9$ for all possible pumping lengths $p$ of $L$ in which case we wouldn't expect the conditions to hold anyway. You can use any $s \in L$ with $|s| \geq p$, for instance $a^pb^pc^p$.

Third: after you have fixed the string for observation, eg. $s = a^pb^pc^p$ as above you must present the $uvxyz$ division under the conditions given is impossible to satisfy. You have to show that every choice of $uvxyz$ fails at least one of the lemma's conditions. The choice of $s$ here matters a lot: as the "center part" of the string is bounded in length – more formally, $|vxy| \leq p$, you know that $v$ and $y$ contain no $a$ symbols, no $c$ symbols, or neither symbol, which gets you the expected result of $L$ being non-context free.

Try again with these notes in mind, and I think you will have an easier time.

$\endgroup$
10
  • $\begingroup$ My logic is that if it fails for 1 example, then it is not CFL. Why is this logic wrong? Can you explain? $\endgroup$
    – supcem
    Nov 11, 2021 at 15:37
  • $\begingroup$ What do you mean by "failing one example"? What failed? You applied the pumping lemma in a wrong way so this one example doesnt imply anything. $\endgroup$
    – nir shahar
    Nov 11, 2021 at 15:41
  • $\begingroup$ @nirshahar i am really confused in applying pumping lemma specially for cfl, can you guide me a simpler approach which is more initutitive? i watched easy theory youtube video but could not clarify this pumping lemma for cfl. i got for regular language tho. but since he uses different method that was of no use really. they say this contains only a's....this contain only bs...I don't get it. what they are trying to do. please guide $\endgroup$
    – supcem
    Nov 11, 2021 at 15:51
  • $\begingroup$ @supcem I recommend you start by learning the simpler pumping lemma for regular languages. The two main mistakes you make here – those being the wrong choice of string (too short) and showing only one non-satisfying $uvxyz$ partition of the string (instead of demonstrating that no satisfying partition exists) – are the kind you could work on understanding with the pumping lemma for regular languages, where you have to make the choice of the string and the proof of impossibility of a satisfying partitioning in a similar manner. $\endgroup$
    – kviiri
    Nov 11, 2021 at 15:55
  • $\begingroup$ I don't see any resources to learn bro. I have 5 textbooks but I can't understand from any of them. Do you have some resources that you used for learning @kviiri. I watched easy theory video for regular language and that messed things up. he taught it so easily but in a different way and taught cfl pumping lemma in different way that i can't comprehend. $\endgroup$
    – supcem
    Nov 11, 2021 at 16:03

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.