Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Notes  >  Theory of Computation  >  Pumping Lemma for Context Free Languages (CFLs)

Pumping Lemma for Context Free Languages (CFLs) | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Part V. Pumping Lemma for Context Free Languages (CFLs)
Consider the following figure:
Pumping Lemma for Context Free Languages (CFLs) | Theory of Computation - Computer Science Engineering (CSE)
From the diagram, we can say that not all languages are context free languages. All context free languages are context sensitive and unrestricted. But all context sensitive and unrestricted languages are not context free from the above diagram.
We have a mechanism to show that some languages are not context free. The pumping lemma for CFLs allow us to show that some languages are not context free.

12 Pumping lemma for CFLs
Let G be a CFG. Then there exists a constant, n such that if W is in L(G) and |W| ≥ n, then we may write W = uvxyz such that,
1. |vy| ≥ 1 that is either v or y is non-empty,
2. |vxy| ≤ n then for all i ≥ 0,
uvixyiz is in L(G).
This is known as pumping lemma for context free languages.

Pumping lemma for CFLs can be used to prove that a language, L is not context free.
We assume L is context free. Then we apply pumping lemma to get a contradiction.
Following are the steps:
Step 1:
Assume L is context free. Let n be the natural number obtained by using the pumping lemma.
Step 2:
Choose W ∈ L so that |W| ≥ n. Write W = uvxyz using the pumping lemma.
Step 3:
Find a suitable k so that uvkxykz /∈ L. This is a contradiction, and so L is not context free.

Examples:
Example 1:
Show that L = {anbncn|n ≥ 1} is not context free.

Step 1:
Assume L is context free. Let n be the natural number obtained by using the pumping lemma.
Step 2:
Choose W ∈ L so that |W| ≥ n. Write W = uvxyz using the pumping lemma.
Let W = anbncn. Then |W| = 3n > n.

Write W = uvxyz, where |vy| ≥ 1, that is, at least one of v or x is not ε.
Step 3:
Find a suitable k so that uvkxykz /∈ L. This is a contradiction, and so L is not context free.
uvxyz = anbncn. As 1 ≤ |vy| ≤ n, v or x cannot contain all the three symbols a, b, c.

i) So v or y is of the form aibj(or bjcj) for some i,j such that i + j ≤ n. or
ii) v or y is a string formed by the repetition of only one symbol among a, b, c.
When v or y is of the form aibj, v2 = aibjaibj(or y2 = aibjaibj). As vis a substring of the form uv2xy2z,we cannot have uv2xy2z of the form ambmcm. So uv2xy2z ∉ L.

When both v and y are formed by the repetition of a single symbol (example: u = ai and v = bfor some iand j, i ≤ n, j ≤ n), the string uxz will contain the remaining symbol, say a1.Also Pumping Lemma for Context Free Languages (CFLs) | Theory of Computation - Computer Science Engineering (CSE) will be a substring of uxz as a1 doesnot occur in v or y. The number of occurrences of one of the other two symbols in uxz is less than n (recall uvxyz = anbncn),and n is the number of occurrences of a1. So uv0xy0z = uxz ∉ L. Thus for any choice of v or y , we get a contradiction. Therefore, L is not context free.

Example 2:
Show that L = {ap|p is a prime number} is not a context free language.

This means, if w ∈ L, number of characters in w is a prime number.
Step 1:
Assume L is context free. Let n be the natural number obtained by using the pumping lemma.
Step 2:
Choose W ∈ L so that |W| ≥ n. Write W = uvxyz using the pumping lemma.
Let p be a prime number greater than n. Then w = ap ∈ L.

We write W = uvxyz
Step 3:
Find a suitable k so that uvkxykz /∈ L. This is a contradiction, and so L is not context free.
By pumping lemma, uv0xy0z = uxz ∈ L.
So |uxz| is a prime number, say q.
Let |vy| = r.
Then |uvqxyqz| = q + qr.
Since, q + qr is not prime, uvqxyqz ∉ L. This is a contradiction. Therefore, L is not context free.

Example 3:
Show that the language L = {anbncn|n ≥ 0} is not context free.

Step 1:
Assume L is context free. Let n be the natural number obtained by using the pumping lemma.
Step 2:
Choose W ∈ L so that |W| ≥ n. Write W = uvxyz using the pumping lemma.
Let W = anbncn.

We write W = uvxyz where |vy| ≥ 1 and |vxy| ≤ n, then
pumping lemma says that uvixyiz ∈ L for all i ≥ 0.

Observations:
a. But this is not possible; because if v or y contains two symbols from {a,b,c} then uv2xy2z contains a ’b’ before an ’a’or a ’c’ before ’b’, then uv2xy2z will not be in L.
b. In other case, if v and y each contains only a’s, b’s or only c’s, then uvixyi cannot contain equal number of a’s, b’s and c’s. So uvixyiz will not be in L.
c. If both v and y contains all three symbols a, b and c, then uv2xy2z will not be in L by the same logic as in observation (a).
So it is a contradiction to our statement. So L is not context free.

Step 3:
Find a suitable k so that uvkxykz ∉ L. This is a contradiction, and so L is not context free.

By pumping lemma, uv0xy0z = uxz ∈ L.
So |uxz| is a prime number, say q.
Let |vy| = r.
Then |uvqxyqz| = q + qr.
Since, q + qr is not prime, uvqxyqz ∉ L. This is a contradiction. Therefore, L is not context free.

The document Pumping Lemma for Context Free Languages (CFLs) | Theory of Computation - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
18 videos|69 docs|44 tests

Top Courses for Computer Science Engineering (CSE)

FAQs on Pumping Lemma for Context Free Languages (CFLs) - Theory of Computation - Computer Science Engineering (CSE)

1. What is the Pumping Lemma for Context Free Languages (CFLs)?
Ans. The Pumping Lemma for Context Free Languages (CFLs) is a fundamental result in formal language theory. It states that any context-free language L has a pumping length p, such that any string w in L with a length of at least p can be divided into five parts, u, v, x, y, and z, satisfying certain conditions. These conditions allow us to "pump" the middle part (v and y) any number of times while still keeping the resulting string in the language L.
2. How does the Pumping Lemma help in proving that a language is not context-free?
Ans. The Pumping Lemma is a powerful tool for proving that a language is not context-free. To prove that a language L is not context-free, we assume that L is context-free and then apply the Pumping Lemma to derive a contradiction. If we can find a string in L that cannot be pumped according to the conditions of the lemma, then we can conclude that the language is not context-free.
3. Can the Pumping Lemma be used to prove that a language is context-free?
Ans. No, the Pumping Lemma cannot be used to prove that a language is context-free. The Pumping Lemma only provides a necessary condition for a language to be context-free, but it is not sufficient to prove context-freeness. It is possible for a language to satisfy the conditions of the Pumping Lemma and still not be context-free. Therefore, other techniques or proofs are required to establish that a language is context-free.
4. What are the conditions that need to be satisfied for the Pumping Lemma to apply?
Ans. The conditions that need to be satisfied for the Pumping Lemma to apply are as follows: 1. For any string w in the language L with a length of at least p (the pumping length), we can divide it into five parts: u, v, x, y, and z. 2. The length of v and y combined is greater than 0 (|vxy| > 0). 3. The length of v and y combined is less than or equal to p (|vxy| ≤ p). 4. For any non-negative integer n, the string uv^nxy^nz must also be in the language L.
5. Can the Pumping Lemma be applied to all languages?
Ans. No, the Pumping Lemma cannot be applied to all languages. It is specifically designed for context-free languages. For languages that are not context-free, the Pumping Lemma may not provide any useful information or may lead to incorrect conclusions. Different types of languages, such as regular languages or recursively enumerable languages, have their own specific techniques and lemmas for analysis and proof.
18 videos|69 docs|44 tests
Download as PDF
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

Exam

,

Semester Notes

,

video lectures

,

Summary

,

Previous Year Questions with Solutions

,

Pumping Lemma for Context Free Languages (CFLs) | Theory of Computation - Computer Science Engineering (CSE)

,

Pumping Lemma for Context Free Languages (CFLs) | Theory of Computation - Computer Science Engineering (CSE)

,

shortcuts and tricks

,

Important questions

,

Sample Paper

,

Viva Questions

,

Extra Questions

,

practice quizzes

,

ppt

,

MCQs

,

Pumping Lemma for Context Free Languages (CFLs) | Theory of Computation - Computer Science Engineering (CSE)

,

Objective type Questions

,

Free

,

study material

,

pdf

,

mock tests for examination

,

past year papers

;