Pumping lemma Computer Science Engineering (CSE) Notes | EduRev

Mock Test Series - Computer Science Engg. (CSE) GATE 2020

Created by: Gate Gurus

Computer Science Engineering (CSE) : Pumping lemma Computer Science Engineering (CSE) Notes | EduRev

The document Pumping lemma Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Mock Test Series - Computer Science Engg. (CSE) GATE 2020.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

Pumping Lemma

There are two Pumping Lemmas, which are defined for
1. Regular Languages, and
2. Context – Free Languages
 
Pumping Lemma for Regular Languages

For any regular language L, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u, v, w ∈ Σ∗, such that x = uvw, and
(1) |uv| ≤ n
(2) |v| ≥ 1
(3) for all i ≥ 0: uviw ∈ L

In simple terms, this means that if a string v is ‘pumped’, i.e., if v is inserted any number of times, the resultant string still remains in L.

Pumping Lemma is used as a proof for irregularity of a language. Thus, if a language is regular, it always satisfies pumping lemma. If there exists at least one string made from pumping which is not in L, then L is surely not regular.
The opposite of this may not always be true. That is, if Pumping Lemma holds, it does not mean that the language is regular.

Pumping lemma Computer Science Engineering (CSE) Notes | EduRev

For example, let us prove L01 = {0n1n | n ≥ 0} is irregular.
Let us assume that L is regular, then by Pumping Lemma the above given rules follow.
Now, let x ∈ L and |x| ≥ n. So, by Pumping Lemma, there exists u, v, w such that (1) – (3) hold.
 
We show that for all u, v, w, (1) – (3) does not hold.
If (1) and (2) hold then x = 0n1n = uvw with |uv| ≤ n and |v| ≥ 1.
So, u = 0a, v = 0b, w = 0c1n where : a + b ≤ n, b ≥ 1, c ≥ 0, a + b + c = n
But, then (3) fails for i = 0
uv0w = uw = 0a0c1n = 0a + c1n ∉ L, since a + c ≠ n.

Pumping lemma Computer Science Engineering (CSE) Notes | EduRev

For above example, 0n1n is CFL, as any string can be the result of pumping at two places, one for 0 and other for 1.
Let us prove, L012 = {0n1n2n | n ≥ 0} is not Context-free.
Let us assume that L is Context-free, then by Pumping Lemma, the above given rules follow.
Now, let x ∈ L and |x| ≥ n. So, by Pumping Lemma, there exists u, v, w, x, y such that (1) – (3) hold.
We show that for all u, v, w, x, y (1) – (3) do not hold.

If (1) and (2) hold then x = 0n1n2n = uvwxy with |vwx| ≤ n and |vx| ≥ 1.
(1) tells us that vwx does not contain both 0 and 2. Thus, either vwx has no 0’s, or vwx has no 2’s. Thus, we have two cases to consider.
Suppose vwx has no 0’s. By (2), vx contains a 1 or a 2. Thus uwy has ‘n’ 0’s and uwy either has less than ‘n’ 1’s or has less than ‘n’ 2’s.
But (3) tells us that uwy = uv0wx0y ∈ L.
So, uwy has an equal number of 0’s, 1’s and 2’s gives us a contradiction. The case where vwx has no 2’s is similar and also gives us a contradiction. Thus L is not context-free.

Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Dynamic Test

Content Category

Related Searches

pdf

,

Free

,

video lectures

,

Sample Paper

,

Exam

,

Objective type Questions

,

Pumping lemma Computer Science Engineering (CSE) Notes | EduRev

,

Extra Questions

,

Important questions

,

Semester Notes

,

ppt

,

Pumping lemma Computer Science Engineering (CSE) Notes | EduRev

,

Summary

,

Pumping lemma Computer Science Engineering (CSE) Notes | EduRev

,

mock tests for examination

,

shortcuts and tricks

,

study material

,

Previous Year Questions with Solutions

,

practice quizzes

,

Viva Questions

,

MCQs

,

past year papers

;