Understanding the Pumping Lemma to Prove Irregularity
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.
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
Pumping Lemma Examples
L>= {aibj: i > j} L>is not regular. We prove it using the Pumping Lemma.
L>= {aibj: i > j} L>is not regular. Fix an arbitrary pumping length n>0.
L>= {aibj: i > j} L>is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>.
L>= {aibj: i > j} L>is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. |s| n
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
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
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
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
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
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
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
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!
L={ww : w in {a,b}*} First, figure out what this language is.
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language?
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language?
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
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?
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
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?
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! ( = )
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?
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!
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?
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!
L={ww : w in {a,b}*} First, figure out what this language is. L = { , aa, bb, aaaa, abab, baba, bbbb, aaaaaa } abaabba|abaabba
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma.
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.
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
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!!!
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
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
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
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
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
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!
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!!!
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
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
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
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!
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!
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
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
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.
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
L = {w1w2 : w1,w2 {a,b}*,|w1|=|w2|} Is it regular?
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
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
