Cs 341 Automata Theory ta: Tazeen Siddiqui Pumping Lemma for Regular Languages What is the pumping lemma for regular languages?
|
|  Yüklə 42.5 Kb.
|
| CS 341 Automata Theory
TA: Tazeen Siddiqui Pumping Lemma for Regular Languages What is the pumping lemma for regular languages? If L is a regular language then there exists N ≥ 1 such that for all strings w in L, where |w| ≥ N, there exist x ,y, z such that w = xyz & |xy| ≤ N & y ≠ epsilon & for all q, xyqz is in L
If q is 0 (called pumping down, since in effect you’re removing the loop), xyqz = aa, which is in L. If q = 2 (if q ≥ 2, it’s called pumping up, since you’re increasing the number of times you take the loop), xyqz = a(bb)2a = abbbba, which is still in the language. (Note that N is a constant, in this case 4. When you’ll be using the pumping lemma, N will be an unknown constant. There’s a difference between the language aNbN and the string aNbN. The N in a language definition is just like any other variable. When you use it to pick a string for the pumping lemma, it’s the pumping constant.) What if L is a finite language? If L is a finite language, it is regular, but you cannot pump it to get other strings that are in the language. This is because the finite state machine doesn’t have any loops in it. If it had a loop then it could accept an infinite number of strings. The pumping lemma is still correct though, it’s just that if L is a finite language then it doesn’t have any strings of length greater than or equal to N. Ok, so how can I use this? You cannot use this to prove that a language is regular because then you would have to show that the pumping lemma works for all q. You can use this to prove that a language is not regular by showing that for all possible ways of breaking up the string into three parts there is at least one q for which the resulting string is not in L. Show me how. Example 1: L = {mmR : m is in {a, b}*} Detailed answer: Pick a string from L in terms of the pumping lemma constant N. w = xyz = aNbNbNaN Given that |xy| ≤ N from the pumping lemma theorem, y must be some number of a’s. y = ap Given that y ≠ epsilon, p > 0. Since x comes before y, it must also be some number of a’s. x = at Since w = xyz, z must be everything else. z = aN-(p+t)bNbNaN
xy2z = at(ap)2aN-(p+t)bNbNaN = at ap ap aN-(p+t) bN bN aN = aN+p bN bN aN Given that p > 0, the number of a’s at the start of the string are not equal to the number of a’s at the end of the string, xy2z is not in L, so L is not regular. Shorter answer (all you have to do in the exam. However, if you can’t do the longer answer, it’s a sign you don’t understand something and may get the short answer wrong. If you don’t understand something, ask): w = aNbNbNaN y = ap Pumping up, q = 2. More a’s at the start than at the end, xy2z is not in L. Therefore L is not regular. Note: If possible pick a w such that the first N characters are from the same symbol, such as aN. Since |xy| ≤ N, picking a string in such a way ensures that there is only one possibility for y. Sometimes it’s not possible to do so. Example 2: L = { aR bM cM: R, M > 0} w = a bN cN (Note you don’t want to pick aN bN cN, because then you’ll be pumping in the a’s and the resulting string will still be in L) case 1: y = a (x can be epsilon) Pump down, q = 0. No a at the start of the start of the string, xy0z is not in L.
Pump up, q = 3. (could’ve picked any value q ≥ 2 for pumping up) More b’s than c’s. xy3z is not in L.
Pump up, q = 2. Out of order a’s and b’s. xy2z is not in L. In all possible cases for y, pumping results in strings that are not in L. Therefore, L is not regular. Example 3: L = {aR bM cM : R, M ≥ 0 } w = bN cN y = bP Pump down, q = 0. Fewer b’s than c’s. Not in L. L is not regular. Example 4: L = {ai bj ck : i = 1 => j > k} You can rewrite L as: L = {ai bj ck : i ≠ 1 or j > k} L complement = {ai bj ck : i = 1 and j ≤ k} w = a bN cN case 1: y = a, pump up, more than 1 a. Not in L complement case 2: y = bp, pump up, more b’s than c’s. Not in L complement. case 3: y = a bt, pump up. Out of order a’s and b’s. Not in L complement. For all possible cases for y, pumping results in strings that are not in L complement. Therefore L complement is not regular. Since regular languages are closed under complementation. If L was regular then its complement would also be regular. Since L complement is not regular, L must also be not regular. |
