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 .
Generally Pumping lemma is used to check the context of grammar. Let’s check this with an example and show how it is checked.
Explore that the language is context free or not.
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 1 − vwx 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 Tutorial
All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd
Wisdomjobs.com is one of the best job search sites in India.