Pumping Lemma for CFG - Automata Theory

What is Pumping Lemma for CFG?

Lemma

If you consider that L is a context-free language, there is a pumping length p in a way that any string w ∈ L of length ≥ p can be written as w = uvxyz, where vy ≠ ε, |vxy| ≤ p, and for all bb.

Applications of Pumping Lemma

Generally Pumping lemma is used to check the context of grammar. Let’s check this with an example and show how it is checked.

Problem

Explore that the language lemma is context free or not.

Solution

Let L is context free. Then, L must satisfy pumping lemma.

For this you need to select a number n of the pumping lemma. Then, take z as 0n1n2n.

Break z into uvwxy, where

|vwx| ≤ n and vx ≠ ε.

So, vwx doesn’t include both 0s and 2s, since the last 0 and the first 2 are at least (n+1) positions apart. Following are the two cases: −

Case 1vwx has no 2s. Then vx has only 0s and 1s. Then uwy, which would have to be in L, has n 2s, but fewer than n 0s or 1s.

Case2− vwx has no 0s.

There will be some contradiction here.

So, its derived that L is not a context-free language.

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Automata Theory Topics