Pumping lemma Theory Of Automata

Presentation About Pumping Lemma Theory Of Automata & Formal Language
By Sir Syed University Of Engineering & Technology Students.

1. AUTOMATA Pumping-lemma

2. Presented By: Hafiz Muhammad Hamza 2017-CS-19 Muhammad Haris Qasim 2017-CS-18 Muhammad Jameel 2017-CS-49 Ragam Muhammad 2017-CS-11 Section : 4A To Miss Mehwish Wahid Theory Of Automata &Formal Languages Department Of Computer Science Sir Syed University Of Engineering & Technology

3. Today’s agenda Introduction Types Examples Advantages Applications

4. INTRODUCTION Pumping Lemma Is Used To Prove That a Language Is Not Regular . It Can Not Be Use to Prove That a Language Is Regular.

5. TYPES OF PUMPING LEMMA Regular languages

6. For regular languages Pumping Lemma Is Used To Prove That a Language Is Not Regular It Can Not Be Use to Prove That a Language Is Regular n simple terms, this means that if a string v is ‘pumped’, i.e., if v is inserted any number of times, the resultant string still remains in L. Pumping Lemma is used as a proof for irregularity of a language. Thus, if a language is regular, it always satisfies pumping lemma. If there exists at least one string made from pumping which is not in L, then L is surely not regular. The opposite of this may not always be true. That is, if Pumping Lemma holds, it does not mean that the language is regular

7. P.L For Regular Language Rules

8. Example

9. Pumping Lemma of Context Free Language Pumping Lemma is Used to Prove that a Language Is Not Context Free . Pumping Lemma for CFL states that for any Context Free Language L, it is possible to find two substrings that can be ‘pumped’ any number of times and still be in the same language. For any language L, we break its strings into five parts and pump second and fourth substring. Pumping Lemma, here also, is used as a tool to prove that a language is not CFL. Because, if any one string does not satisfy its conditions, then the language is not CFL.

10. P.L For CFG Rules Let L(G) Is CFG Then Following Condition Must Be Satisfied. Steps Every Z ∈ L(G) With |Z|>=n n is natural Number And Z= uvwxy For String Divide Into Five Parts. | vx |>=1 | uwx |<=n u v^k w x^k y ∈ L for All K>=0

11. Example Prove L={ a^i,b^i,c^I / i >=1} is Not CFG. Assume L Is CFG & n is Natural Number n=10 L={ abc,aabbcc,aaabbbccc,aaaabbbbcccc ….} Z= aaaabbbbcccc |z|>=n v & x Contain Some Symbols u= aa , v= aa , w= bbbb , x=c, y= ccc u v^i w x^i y ∈ L K>=0 K=1 aaaabbbbcccc ∈L K=2 aaaaaabbbbccccc ! ∈ L

12. ADVANTAGES OF PUMPING-LEMMA Pumping lemma for regular languages, the fact that all sufficiently long strings in such a language have a substring that can be repeated arbitrarily many times, usually used to prove that certain languages are not regular. Pumping lemma for context-free languages, the fact that all sufficiently long strings in such a language have a pair of substrings that can be repeated arbitrarily many times, usually used to prove that certain languages are not context-free Pumping lemma for indexed languages

13. Applications of Pumping Lemma Pumping lemma is a negative test. It can be used in applications like Showing an invalid move in game of chess. As the move may not obey rules of game.

14. Applications of Pumping Lemma pumping lemma can be applied to prove that the inputted move is invalid. Moreover, some Power stations also use this lemma for determining the cut off temperatures to be kept in furnaces. For an example, say pumping lemma can answer to why the temperature shouldn’t go beyond 250 Degrees, etc. Thus, in a nutshell, pumping lemma has variety of applications in practical engineering.

15. REFRENCES https://en.wikipedia.org/wiki/Pumping_lemma https://www.geeksforgeeks.org/theory-of-computation-pumping-lemma/ https://www.sanfoundry.com/automata-theory-pumping-lemma-regular-languages