Pumming Lemma

It is algorithm related to subject Theory of Computing

1. ACTIVE LEARNING ASSIGNMENT FOR THE SUBJECT “Theory of computation” PUMPING LEMMA Guided By : - Rimi Gupta (Assistance prof.) Prepared By :- Hemant H. Chetwani (130410107010 TY CE-II)

2. Non-regular languages (Pumping Lemma)

3. Regular languages Non-regular languages

4. How can we prove that a language is not regular? Prove that there is no DFA or NFA or RE that accepts Difficulty: this is not easy to prove ( since there is an infinite number of them) Solution: use the Pumping Lemma !!!

5. The Pigeon hole Principle

6. pigeons pigeonholes

7. A pigeonhole must contain at least two pigeons

8. ........... ........... pigeons pigeonholes

9. The Pigeonhole Principle ........... pigeons pigeonholes There is a pigeonhole with at least 2 pigeons

10. The Pigeon hole Principle and DFAs

11. Consider a DFA with states

12. Consider the walk of a “long’’ string: A state is repeated in the walk of (length at least 4)

13. Pigeons: Nests: (Automaton states) Are more than Walk of The state is repeated as a result of the pigeonhole principle (walk states) Repeated state

14. ...... ...... Repeated state Walk of .... .... .... Arbitrary DFA If , by the pigeonhole principle, a state is repeated in the walk In General:

15. Walk of Pigeons: Nests: (Automaton states) Are more than (walk states) .... .... .... .... ....

16. The Pumping Lemma

17. Take an infinite regular language There exists a DFA that accepts states (contains an infinite number of strings)

18. (number of states of DFA) then, at least one state is repeated in the walk of ...... ...... Take string with Walk in DFA of Repeated state in DFA

19. Take to be the first state repeated .... There could be many states repeated .... .... Second occurrence First occurrence Unique states One dimensional projection of walk :

20. .... .... .... Second occurrence First occurrence One dimensional projection of walk : We can write

21. ... ... In DFA: ... ... contains only first occurrence of

22. The string is accepted In General: ... ... ... Follow loop times ...

23. Therefore: Language accepted by the DFA ... ... ... ...

24. In other words, we described: The Pumping Lemma !!!

25. The Pumping Lemma: Given a infinite regular language there exists an integer for any string with length we can write with and such that: (critical length)

26. Applications of the Pumping Lemma

27. Suppose you want to prove that An infinite language is not regular 1. Assume the opposite: is regular 2. The pumping lemma should hold for 3. Use the pumping lemma to obtain a contradiction 4. Therefore, is not regular

28. Theorem: The language is not regular Proof: Use the Pumping Lemma Example of Pumping Lemma application Assume for contradiction that is a regular language Since is infinite we can apply the Pumping Lemma

29. with lengths From the Pumping Lemma: we can write Thus:

30. From the Pumping Lemma: Thus:

31. BUT: CONTRADICTION!!!

32. Our assumption that is a regular language is not true Conclusion: is not a regular language Therefore: