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.....