Understanding the Pumping Lemma to Prove Irregularity

Slide Note
Embed
Share

Utilizing the Pumping Lemma to demonstrate the irregularity of languages where the condition L>= {aibj, i>j} is not satisfied. The process involves fixing a pumping length, choosing a suitable string from L, and exploring possible splittings of the string to show irregularity.


Uploaded on Jul 29, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Pumping Lemma Examples

  2. L>= {aibj: i > j} L>is not regular. We prove it using the Pumping Lemma.

  3. L>= {aibj: i > j} L>is not regular. Fix an arbitrary pumping length n>0.

  4. L>= {aibj: i > j} L>is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>.

  5. L>= {aibj: i > j} L>is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. |s| n

  6. L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. aaa aabb b n n+1

  7. L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. Consider all possible splittings of s in x,y,z with the desired properties. aaa aabb b n n+1

  8. L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. Consider all possible splittings of s in x,y,z with the desired properties. |xy| n |y| 1 aaa aabb b n n+1

  9. L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. Consider all possible splittings of s in x,y,z with the desired properties. |xy| n |y| 1 aaa aabb b n n+1

  10. L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. Consider all possible splittings of s in x,y,z with the desired properties. Y |xy| n |y| 1 aaa aabb b n+1 n

  11. L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. Consider all possible splittings of s in x,y,z with the desired properties: y = am, 1 m n. Y aaa aabb b n+1 n

  12. L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. Consider all possible splittings of s in x,y,z with the desired properties: y = am, 1 m n. xz =an+1-mbn L>. aaabb b n+1-m n n

  13. L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. Consider all possible splittings of s in x,y,z with the desired properties: y = am, 1 m n. xz =an+1-mbn L>. So L> is not regular!

  14. L={ww : w in {a,b}*} First, figure out what this language is.

  15. L={ww : w in {a,b}*} First, figure out what this language is. A string in the language?

  16. L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab

  17. L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language?

  18. L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa

  19. L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language?

  20. L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language? abbb

  21. L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language? abbb Is in the language?

  22. L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language? abbb Is in the language? YES! ( = )

  23. L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language? abbb Is in the language? YES! ( = ) Is aa in the language?

  24. L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language? abbb Is in the language? YES! ( = ) Is aa in the language? YES!

  25. L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language? abbb Is in the language? YES! ( = ) Is aa in the language? YES! Is a in the language?

  26. L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language? abbb Is in the language? YES! ( = ) Is aa in the language? YES! Is a in the language? NO!

  27. L={ww : w in {a,b}*} First, figure out what this language is. L = { , aa, bb, aaaa, abab, baba, bbbb, aaaaaa } abaabba|abaabba

  28. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma.

  29. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. First fix an arbitrary number n>0 to be the pumping length.

  30. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language

  31. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Choose wisely!!!

  32. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = a2n aaa aaa|aaa aaa n n

  33. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = a2n For x = , y = a2, z = a2n-2 z y aaa aaa|aaa aaa n n

  34. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = a2n For x = , y = a2, z = a2n-2 y y z aaaaa aa|aaaa aaa n+1 L n+1

  35. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = a2n For x = , y = a2, z = a2n-2 y y y z aaaaaaa a|aaaaa aaa n+2 L n+2

  36. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = a2n For x = , y = a2, z = a2n-2 z a aaaa|aa aaa n-1 L n-1

  37. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = a2n For x = , y = a2, z = a2n-2, there is no i: xyiz L!

  38. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = a2n For x = , y = a2, z = a2n-2, there is no i: xyiz L! s = a2ndoesn t work!!!

  39. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = (ab)2n abab abab|abab abab n n

  40. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = (ab)2n For x = , y = abab, z = (ab)2n-2 y z abab abab|abab abab n n

  41. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = (ab)2n For x = , y = abab, z = (ab)2n-2 y y z abababab ab|ababab abab n+1 L n+1

  42. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = (ab)2n For x = , y = abab, z = (ab)2n-2 For any i, xyiz = (ab)2i(ab)2n-2 = (ab)2(i-n-2) L!

  43. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = (ab)2n For x = , y = abab, z = (ab)2n-2 For any i, xyiz = (ab)2i(ab)2n-2 = (ab)2(i-n-2) L! s = (ab)2ndoesn t work!

  44. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Use s = anbanb aaaa aab|aaaa...aab n n

  45. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Use s = anbanb For any splitting of s in x,y,z with the desired properties: aaaa aab|aaaa...aab n n

  46. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language Use s = anbanb For any splitting of s in x,y,z with the desired properties: y = amwith 1 m n.

  47. L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language Use s = anbanb For any splitting of s in x,y,z with the desired properties: y = amwith 1 m n. Observe that xy2z = am+nbanb is not in L QED

  48. L = {w1w2 : w1,w2 {a,b}*,|w1|=|w2|} Is it regular?

  49. L = {w1w2 : w1,w2 {a,b}*,|w1|=|w2|} Is it regular? A first attempt to design a FA a,b a,b a,b a,b ... q10 q11 q12 q13 q1n a,b a,b a,b a,b ... q2n-1 q2n-2 q2n-3 q2n q20

  50. L = {w1w2 : w1,w2 {a,b}*,|w1|=|w2|} Is it regular? A first attempt to design a FA fails! a,b a,b a,b a,b ... q10 q11 q12 q13 q1n a,b a,b a,b a,b ... q2n-1 q2n-2 q2n-3 q2n q20

Related


More Related Content