1.10. pumping lemma for regular sets

pumping lemma for regular sets

1. Pumping Lemma for Regular sets Sampath Kumar S, AP/CSE, SECE

2. Pumping for Regular Set: Theorem: Let L be a regular set. Then there exists a constant  ‘n’  such that for every string  W  in  L  − |W| ≥ n We can break  W  into 3 strings, W = X Y Z,  such that: |Y| > 0 |XY| ≤ n For all k ≥ 0, the string XY k Z is also in L . Note: Select  k  such that the resulting string is not in  L . 7/22/2016 Sampath Kumar S, AP/CSE, SECE 2

3. Applications of Pumping Lemma: Pumping Lemma is to be applied to show that certain languages are not regular. It should never be used to show a language is regular. If  L  is regular, it satisfies Pumping Lemma. If  L  is non-regular, it does not satisfy Pumping Lemma. 7/22/2016 3 Sampath Kumar S, AP/CSE, SECE

4. Method to prove that a language L is not regular At first, we have to assume that  L  is regular. So, the pumping lemma should hold for  L. Use the pumping lemma to obtain a contradiction − Select  W  such that  |W| ≥ n Select  Y  such that  |Y| > 0 Select  X  such that  |XY| ≤ n Assign the remaining string to  Z. Select  k  such that the resulting string is not in  L. Hence L is not regular 7/22/2016 Sampath Kumar S, AP/CSE, SECE 4

5. Problems to Discuss: 45. Prove that  L = { a i b i  | i ≥ 0}  is not regular. Solution At first, we assume that  L  is regular and  n  is the number of states. Let w = a n b n . Thus |W| = 2n ≥ n. By pumping lemma, let W = XYZ, where |XY|≤ n. Let X = a p , Y = a q , and Z = a r b n , where p + q + r = n.p ≠ 0, q ≠ 0, r ≠ 0. Thus |y|≠ 0 Let k = 2. Then xy 2 z = a p a 2q a r b n . Number of  a’ s = (p + 2q + r) = (p + q + r) + q = n + q Hence, xy 2 z = a n+q  b n . Since q ≠ 0, xy 2 z is not of the form a n b n . Thus, xy 2 z is not in L. Hence L is not regular. 7/22/2016 5 Sampath Kumar S, AP/CSE, SECE

6. Problems to Discuss: 47. Prove that  L = { ww R |w ∈ { a,b }}  is not regular. 48. Prove that  L = {0 n 1 n 2 n |n>1 }  is not regular. 49. Prove that  L = {0 n 1 m |m>n & m,n >0 }  is not regular 7/22/2016 Sampath Kumar S, AP/CSE, SECE 6

7. 7/22/2016 Sampath Kumar S, AP/CSE, SECE 7

8. நன்றி  7/22/2016 Sampath Kumar S, AP/CSE, SECE 8