Prove that the perfect squares in base 10 do not consitute a regular language. The idea behind the pumping lemma is that every regular language has a p-value. (The p-value is actually the number of states in its finite automaton.) Every string in the language whose length is > p can be pumped. Every string whose length is > p can be divided into three strings: uvw, length (uv) <= p, length (v) > 0, such that uv*w are all in the language, too. (uw, uvw, uvvw, uvvvw, uvvvvw, etc.) the idea is that if a string is long enough, it will have to hit some states in the finite automaton more than once, meaning it will have to cycle somewhere in the automaton, so if a certain substring make a cycle in the automaton, you can repeat that substring as often as you like, going around as often you like, knowing that your extended string will still hit the accept state and thus be part of the language. An easy example: even numbers in base 10. This can be done with 2 states. (one state for "odd so far" one state for "even so far"), so its p-value is 2. So, let's I grab any valid string of length >= 2 (I will grab "12"), You should be able to break this up into uvw such that length (uv) <= 2, length (v) > 0, and uv*w is always in the language. u is empty v is "1" w is "2" 1*2 is totally always even. I can pump that 1 as many times as I want and always end up with a valid string in the language. Another example: All strings with an even number of zeroes and an odd number of 1's. We showed that this can be done in four states, so the p-value of this language is 4. 11100 uvw...length of (uv) is <= 4. len (v) > 0, and uv*w is always in the language. u = 1 v = 11 w = 00 1(11)*00 10000 u = 1 v = 00 w = 00 1(00)*00 10101 u = empty v = 1010 w = 1 (1010)*1 So, to prove that a language is NOT regular, you want to demonstrate that there are long strings that cannot be pumped. Short strings don't count. If a string is smaller than the p-value, then there might not be a loop in the finite automaton anyway. To prove that a language is not regular, you ASSUME that the language is regular and has a p-value. (What is that p-value? You don't know, you just assume it has one and use that value...even without knowing what it is.) Balanced parentheses. Assume there is a p-value. I don't know what it is, but find a string longer than p. I'm going to use the string of p ('s followed by p )'s. This is totally in the language. If this language were regular, I should be able to pump it. p ('s followed by p )'s. There are 2p characters in this string. I'll split it into uvw length(uv) <= p length(v) > 0. Since length (uv) <= p, and the first p characters are ('s. All of u and all of v must be ('s. uv*w: v must contain at least 1 (, so everytime I pump it, I add ('s without adding any )'s. So, if I even pump it once, I have a string not in the language. Thus, this p-value does not work, thus no p-value works, so this language has no p-value, and so cannot be regular. I don't have to prove that NO string can be pumped. I just have to find one string that can't be pumped. The language of base 10 perfect squares: 0, 1, 4, 9, 16, 25, 36, 49, 64, ... 1 is in the language, so pump 1. 11 is not. 111 is not. 1111 is not. But this doesn't work as an argument, because not being able to pump a short string means nothing. Your starting string must be longer than the p-value. So, since you don't know the p-value, you need to do this: for ANY p, show how you can find a string in the language (in other words, a perfect square) whose length is greater than p, and still cannot be pumped. What is 9x9? What is 99x99? What is 999x999? What is 9999x9999? Can you see a pattern there that you can use? How would you prove that the language of base 10 prime numbers {2,3,5,7,11,13,17,19,...} is not regular? Suppose this language is regular, and so has a p-value. Can you come up with a prime number whose length is greater than p and which cannot be pumped? In base 10, numbers are divisible by 3 whenever the sum of their digits is divisible by 3. 81: 8+1 = 9, 9 is divisible by 3, so 81 is. 12345: 1+2+3+4+5 = 15: 1+5 = 6. 6 is divisible by 3, so 15 is, so 12345 is. 12345/3 = 4115. 97: 9+7 = 16: 1+6 = 7. 7 is not divisible by 3, so 16 isn't so 97 isn't. In fact, 7%3 = 1, so 16%3=1, so 97%3 = 1. 97 = 3x32 + 1. 573928365 % 3: 5+7+3+9+2+8+3+6+5 = 48: 4+8 = 12: 1+2 = 3. 3%3 = 0, so the original number is divisible by 3. Divisibility by 2: If the 1's digit is divisible by 2, the whole number is. Divisibility by 4: Double the 10's digit and add the 1's digit. This value is divisible by 4 when the whole number is. So, 2023: 2x2+3 = 7. 7%4=3, so the whole number is. Divisibility by 5: Check the last digit. Divisibility by 6: Add the last digit to 4 times the sum of all the other digits, and check that for divisiblity by 6. 4*2 + 4*0 + 4*2 + 3 = 19. 4*1 + 9 = 13. 4*1 + 3 = 7. 7%6 = 1, so 2023 % 6 = 1. Divisibility by 7: 1's + 3 * 10's + 2 * 100's + 6* 1000's + 4* 10000's + 5* 100000's, repeating this pattern 1-3-2-6-4-5. Except for 3, no prime number has a digit sum that is divisible by 3...if it did, the number itself would have been divisible by 3. 2,3,5,7, 11, 17, 19, 23 Let's say that p is our p-value. Find some prime longer than p digits whose first digit is 1. There are an infinite number of these. Then pump the 1. If our prime is 1. Then look at these numbers: 1, 11, 111. One of these three numbers has a digit sum divisible by 3. The one divisible by 3, can't be prime. Regular grammars: Every regular expression can be expressed as a context-free grammar. (Every regular language is also context-free.) The idea behind a regular grammar, is that every production rule contains no more than one nonterminal on the right, and that nonterminal is the last symbol on the right. S->1S S->2S S->3S S->4S S->5S S->6S S->7S S->8S S->9S S->0S S->0 S->2 S->4 S->6 S->8 Generate 912 S 9S 91S 912 How would we write 10*1 as a regular grammar? A->1B B->0B B->1 How would we write (1*01*)* as a regular grammar? S->empty S->1S S->0T T->1T T->S A->empty A->B B->1B B->0D D->1D D->A How would we write the language of 0's and 1's with an even number of zeroes and an odd number of ones as a regular grammar? Ha ha ha ha ha ha.