Pumping Lemma: Solutions to Practice Problems

Solutions to Practice Problems Pumping Lemma 1. L = { akbk | k $ 0} see notes 2. L = {ak | k is a prime number} Proof by contradiction: Let us assume L is regular. Clearly L is infinite (there are infinitely many prime numbers). From the pumping lemma, there exists a number n such that any string w of length greater than n has a “repeatable” substring generating more strings in the language L. Let us consider the first prime number p $ n. For example, if n was 50 we could use p = 53. From the pumping lemma the string of length p has a “repeatable” substring. We will assume that this substring is of length k $ 1. Hence: ap ap + k ap+2k 0 L 0 L 0 L, etc. and as well as It should be relatively clear that p + k, p + 2k, etc., cannot all be prime but let us add k p times, then we must have: ap + pk 0 L, of course ap + pk = ap (k + 1) so this would imply that (k + 1)p is prime, which it is not since it is divisible by both p and k + 1. Hence L is not regular. 3. L = {anbn+1} Assume L is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose apbp+1. Its length is 2p + 1 $ p. Since the length of xy cannot exceed p, y must be of the form ak for some k > 0. From the pumping lemma ap-kbp+1 must also be in L but it is not of the right form. Hence the language is not regular. Note that the repeatable string needs to appear in the first n symbols to avoid the following situation: assume, for the sake of argument that n = 20 and you choose the string a10 b11 which is of length larger than 20, but |xy| # 20 allows xy to extend past b, which means that y could contain some b’s. In such case, removing y (or adding more y’s) could lead to strings which still belong to L. 4. L = {anb2n } Assume L is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose apb2p. Its length is 3p $ p. Since the length of xy cannot exceed p, y must be of the form ak for some k > 0. From the pumping lemma ap-kb2p must also be in L but it is not of the right form. Hence the language is not regular. 5. TRAILING-COUNT as any string s followed by a number of a’s equal to the length of s. Assume L is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose bpap. Its length is 2p $ p. Since the length of xy cannot exceed p, y must be of the form bk for some k > 0. From the pumping lemma bp-kap must also be in L but it is not of the right form. Hence the language is not regular. 6. EVENPALINDROME = { all words in PALINDROME that have even length} Same as #2 above, choose anbban. 7. ODDPALINDROME = { all words in PALINDROME that have odd length} Same as #2 above, choose anban. 8. DOUBLESQUARE = { anbn where n is a square } Assume DOUBLESQUARE is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose ap*pbp*p. Its length is 2p2 $ p. Since the length of xy cannot exceed p, y must be of the form ak for some k > 0. Let us add y p times. From the pumping lemma ap*p+pkbp*p = ap(p + k)bp*p must also be in L but it is not of the right form. Hence the language is not regular. 9. L = { w | w 0 {a, b}*, w = wR} Proof by contradiction: Assume L is regular. Then the pumping lemma applies. From the pumping lemma there exists an n such that every w 0 L longer than n can be represented as x y z with |y| 0 and |x y| # n. Let us choose the palindrome anban. Again notice that we were clever enough to choose a string which: a. has a center mark which is not a (otherwise when we remove or add y we would be left with an acceptable string) b. has a first portion on length n which is all a’s (so that when we remove or add y it will create an imbalance). Its length is 2n + 1 $ n. Since the length of xy cannot exceed n, y must be of the form ak for some k > 0. From the pumping lemma an-k b an must also be in L but it is not a palindrome. Hence L is not regular. 10. L = { w 0 {a, b}* | w has an equal number of a’s and b’s} Let us show this by contradiction: assume L is regular. We know that the language generated by a*b* is regular. We also know that the intersection of two regular languages is regular. Let M = (anbn | n $ 0} = L(a*b*) 1 L. Therefore if L is regular M would also be regular. but we know tha M is not regular. Hence, L is not regular. 11. L = { w wR | w 0 {a, b}* } see # 7 12. L = { 0n | n is a power of 2 } Assume L is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose n = 2p. Since the length of xy cannot exceed p, y must be of the form 0k for some 0 < k #p. From the pumping lemma 0m where m = 2p+ k must also be in L. We have 2p < 2p + k # 2 p + p < 2 p + 1 Hence this string is not of the right form. Hence the language is not regular. 13. L = {a2kw | w 0 {a, b}*, |w| = k} Assume L is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose a2pbp. Its length is 3p $ p. Since the length of xy cannot exceed p, y must be of the form ak for some k > 0. From the pumping lemma a2p-kbp must also be in L but it is not of the right form since the number of a’s cannot be twice the number of b’s (Note that you must subtract not add , otherwise some a’s could be shifted into w). Hence the language is not regular. 14. L = {akw | w 0 {a, b}*, |w| = k} Assume L is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose apbp. Its length is 2p $ p. Since the length of xy cannot exceed p, y must be of the form ak for some k > 0. From the pumping lemma ap-kbp must also be in L but it is not of the right form since the number of a’s cannot be equal to the number of b’s (Note that you must subtract not add , otherwise some a’s could be shifted into w). Hence the language is not regular. 15. L = {anbl | n # l} Assume L is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose apbp. Its length is 2p $ p. Since the length of xy cannot exceed p, y must be of the form ak for some k > 0. From the pumping lemma ap+k bp must also be in L but it is not of the right form since the number of a’s exceeds the number of b’s (Note that you must add not subtract, otherwise the string would be OK). Hence the language is not regular. 16. L = {anblak | k = n + l} Assume L is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose apbap+1. Its length is 2p+2 $ p. Since the length of xy cannot exceed p, y must be of the form am for some m > 0. From the pumping lemma ap-mbap+1 must also be in L but it is not of the right form. Hence the language is not regular. 17. L = {vak+1 | v 0 {a, b}*, |v| = k} Assume L is regular. From the pumping lemma there exists an n such that every w 0 L such that |w| $ n can be represented as x y z with |y| 0 and |xy| # p. Let us choose bnan+1. Its length is 2n+1 $ n. Since the length of xy cannot exceed n, y must be of the form bk for some k > 0. From the pumping lemma if we add two y to the original string bn+2k an+1 must also be in L but that string is of length 2n+2k+1 and v would have to be bn+k to fit the pattern the rest of the string would then be bk ak+1 which is not of the right form. Hence the language is not regular. 18. L = {va2k | v 0 {a, b}*, |v| = k} Assume L is regular. From the pumping lemma there exists a n such that every w 0 L such that |w| $ n can be represented as x y z with |y| 0 and |xy| # n. Let us choose bna2n. Its length is 3n $ n. Since the length of xy cannot exceed n, y must be of the form bk for some k > 0. From the pumping lemma bn+k an must also be in L but it is not of the right form since the number of a’s exceeds the number of b’s and we cannot move any b’s on the a side (Note that you must add not subtract, otherwise the string would be OK by shifting a’s to the b side). Hence the language is not regular. 19. L = {ww | w 0 {a, b}*} Assume L is regular. From the pumping lemma there exists an n such that every w 0 L such that |w| $ n can be represented as x y z with |y| 0 and |xy| # n. Let us choose anbnanbn. Its length is 4n $ n. Since the length of xy cannot exceed n, y must be of the form ak for some k > 0. From the pumping lemma an+kbnanbn must also be in L but it is not of the right form since the middle of the string would be in the middle of the b which prevents a match with the beginning of the string. Hence the language is not regular. 20. L = { an! | n $ 0} Proof by contradiction: Let us assume L is regular. From the pumping lemma, there exists a number p such that any string w of length greater than p has a “repeatable” substring generating more strings in the language L. Let us consider ap! (unless p < 3 in which case we chose a3! ). From the pumping lemma the string w has a “repeatable” substring. We will assume that this substring is of length k $ 1. From the pumping lemma ap!-k must also be in L. For this to be true there must be j such that j! = m! - k But this is not possible since when p > 2 and k # m we have m! - k > (m - 1)! Hence L is not regular. 21. L = { anbl | n l} Proof by contradiction: Let us assume L is regular. From the pumping lemma, there exists a number p such that any string w of length greater than p has a “repeatable” substring generating more strings in the language L. Let us consider n = p! and l = (p+1)! From the pumping lemma the resulting string is of length larger than p and has a “repeatable” substring. We will assume that this substring is of length k $ 1. From the pumping lemma we can add y i-1 times for a total of i ys. If we can find an i such that the resulting number of a’s is the same as the number of b’s we have won. This means we must find i such that: m! + (i - 1)*k = (m + 1)! or (i - 1) k = (m + 1) m! - m! = m * m! or i = (m * m!) / k +1 but since k < m we know that k must divide m! and that (m * m!) / k must be an integer. This proves that we can choose i to obtain the above equality. Hence L is not regular. 22. L = {anblak | k > n + l} Assume L is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose apbap+2. Its length is 2p+3 $ p. Since the length of xy cannot exceed p, y must be of the form am for some m > 0. From the pumping lemma ap+2mbap+2 must also be in L but it is not of the right form since p+2m+1 > p+2. Hence the language is not regular. 23. L = {anblck | k n + l} Assume L is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose ap! bp! a(p+1)! . Its length is 2p!+(p+1)! $ p. Since the length of xy cannot exceed p, y must be of the form am for some m > 0. From the pumping lemma any string of the form xyi. z must always be in L. If we can show that it is always possible to choose i in such a way that we will have k = n + l for one such string we will have shown a contradiction. Indeed we can have p!+(i-1)m + p! = (p+1)! if we have i = 1 + ((p+1)! - 2 p!)/ m Is that possible? only if m divides ((p+1)! -2 p! ((p + 1)! - 2 * (p)! = (p + 1 - 2) p! and since m # p m is guaranteed to divide p!. Hence i exists and the language is not regular. 24. L = {anblak | n = l or l k} Proof by contradiction: Let us assume L is regular. From the pumping lemma, there exists a number p such that any string w of length greater than p has a “repeatable” substring generating more strings in the language L. Let us consider w = apbpap. From the pumping lemma the string w, of length larger than p has a “repeatable” substring. We will assume that this substring is of length m $ 1. From the pumping lemma we can remove y and the resulting string should be in L. However, if we remove y we get ap - mbpap. But this string is not in L since p-m p and p = p. Hence L is not regular. 25. L = {anba3n | n $ 0} Assume L is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose apba3p. Its length is 4p+1 $ p. Since the length of xy cannot exceed p, y must be of the form ak for some k > 0. From the pumping lemma ap-kba3p must also be in L but it is not of the right form. Hence the language is not regular. 26. L = {anbncn | n $ 0} Assume L is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose apbpcp. Its length is 3p $ p. Since the length of xy cannot exceed p, y must be of the form ak for some k > 0. From the pumping lemma ap-kbpap must also be in L but it is not of the right form. Hence the language is not regular. 27. L = {aibn | i, n $ 0, i = n or i = 2n} Assume L is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose apbp. Its length is 2p $ p. Since the length of xy cannot exceed p, k y must be of the form a for some k > 0. From the pumping lemma ap-kap must also be in L but it is not of the right form. Hence the language is not regular. 28. L = {0k10k | k $ 0 } Assume L is regular. From the pumping lemma there exists an n such that every w 0 L such that |w| $ n can be represented as x y z with |y| 0 and |xy| # n. Let us choose 0n10n. Its length is 2n+1 $ n. Since the length of xy cannot exceed n, y must be of the form 0p for some p > 0. From the pumping lemma 0n-p10n must also be in L but it is not of the right form. Hence the language is not regular. 29. L = {0n1m2n | n, m $ 0 } Assume L is regular. From the pumping lemma there exists a p such that every w 0 L such that |w| $ p can be represented as x y z with |y| 0 and |xy| # p. Let us choose 0p12p. Its length is 2p+1 $ p. Since the length of xy cannot exceed p, y must be of the form 0p for some p > 0. From the pumping lemma 0n-p12n must also be in L but it is not of the right form. Hence the language is not regular.