What is pumping lemma? What are the applications of pumping lemma?


Pumping lemma: Pumping lemma a powerful technique which is proving certain language non-regular. It is also used to generate whether the language accepted by a given FA is a finite or infinite.
Mathematically pumping lemma for regular language. Let L be regular set. Then there is a constant n, depending on L, such that if z is in L & | z | ≥ n, then we may write z = uvw such that,
| v | ≥ 1
| uv | ≤ n &
for all i ≥ 0 uvw is in L.
The applications of pumping lemma: 
The pumping lemma is extremely useful in proving that certain sets are non-regular. The general methodology followed during its applications is –
(i) Select the language L we wish to prove non-regular.
(ii) Then picks n, the constant mentioned in the pumping lemma.
(iii) Select a string z in L. The choice may depend implicitly on the value of n chosen in (ii).
(iv) Now break z into u, v and w, subject to the constraints that | uv | ≤ n and | v | ≥ 1.
(v) We achieve a contradiction to the pumping lemma by showing for any u, v and w determined by the adversary, that there exists an i for which u vi w is not in L. It may then be concluded that L is not regular.
Our selection of i may depend on n, u, v and w.


No comments

Dear Members, Thanks for Your Comments. We must be reply your comment answer as soon as possible. Please Stay with us.....

Theme images by ideabug. Powered by Blogger.