[PDF] application of z transform in digital filters
[PDF] application of z transform in electronics and communication engineering
[PDF] application of z transform in image processing
[PDF] application of z transform in signals and systems
[PDF] application of z transform pdf
[PDF] application of z transform to solve difference equation
[PDF] application of z transform with justification
[PDF] application pour apprendre l'anglais gratuit sur pc
[PDF] application security risk assessment checklist
[PDF] applications of composite materials
[PDF] applications of dft
[PDF] applications of exponential and logarithmic functions pdf
[PDF] applications of therapeutic drug monitoring
[PDF] applied environmental microbiology nptel
[PDF] applied environmental microbiology nptel pdf
Notes on Pumping Lemma
Finite Automata Theory and Formal Languages { TMV027/DIT321
Ana Bove, March 5th 2018
In the course we see two dierent versions of the Pumping lemmas, one for regular languages and one for context-free languages. In what follows we explain how to use these lemmas.
1 Pumping Lemma for Regular Languages
We can use a variety of tools in order to show that a certain language is regular. For example, we can give a nite automaton that recognises the language, a regular expression that generates the language, or use closure properties to show that the language is regular. But how to formally show that a language is NOT regular? We could still use clo- sure properties, but this is not always easy. Formally showing that there is no possible automaton that could recognise the language nor a possible regular expression that could generate it is even more dicult. Instead we can try to use thePumping lemma for regular languageswhich says: LetLbe a regular language. Then, there exists a constantn|which depends onL|such that for every stringw2 Lwithjwj>n, it is possible to breakw into three stringsx;yandzsuch thatw=xyzand
1.jxyj6n;
2.y6=;
3.8k>0: xykz2 L.
Note that the lemma states certain things to happen whenever a language is regular. Note also that the stringyto be \pump" is always placed within the rstnsymbols in the word. When we want to prove that a certain languageLis NOT regular, we start by assuming the language is regular. Then, the Pumping lemma for regular languages must apply. We reason now using the information provided by the lemma until we arrive to a contradiction. Since the only assumption we have made in the reasoning was that the languageLwas regular, then this must the source of the problem and thus, we can conclude thatLis
NOT regular.
More concretely, if we want to prove thatLis not regular we proceed as follows:
1. We assume thatLis regular; hence the Pumping lemma for regular languages must
apply. 1
2. The Pumping lemma tells us that there must exist a constant depending onL; let
us give a name to this constant, sayn, so we can easily refer to it. Only now we can start using this constant!
3. Now we know that certain things must hold whenever we have a word in the language
which is longer than the constantn. Let us continue by picking a concrete wordw in the language which is larger thann. Observe that it needs to be clear that indeed jwj>n, otherwise this will need to be shown. In practice, since we do not really know the value ofn,wwill probably need to usenas part of its denition in order to actually guarantee thatjwj>n!
4. From the lemma we know that this wordwcan be split into three partsx,yandz.
Observe that we do NOT know exactly how these parts look like, only thatw=xyz, jxyj6nandy6=, which is the information provided by the lemma!
5. According to the Pumping lemma it must also be the case that for allk>0 then
xy kz2 L. That is, if we \pump" the partyas many times as we wish, then the word xy kzmust still belong to the languageL. This means that if we nd at least ONE valuekfor whichxykzdoes NOT belong toL, then we arrive to a contradiction sincexykzmust be inLfor ANYk! Let us now look at the use of the Pumping lemma for regular languages in more detail with the help of some examples. In what follows, #
0(w) is the number of occurrences of
the symbol 0 in the wordwand #1(w) is the number of occurrences of 1 inw.
1.1L1=f0i1i2iji >0gis not a Regular Language
Let us assume the languageL1is regular. Then the Pumping lemma for regular languages applies forL1.
Letnbe the constant given by the Pumping lemma.
Letw= 0n1n2n. Clearlyw2 L1andjwj>n.
By the lemma we know thatw=xyzwithjxyj6nandy6=.
Given our choice ofw, and given thatxyis located at the beginning of the word and that it is not longer thann, thenxyshould contain only 0's. Sincey6=thenyshould contain at least one 0 and sincexyshould contain only 0's thenywill also contain only 0's! Then fork= 2, the wordxy2z=xyyzwill contain more 0's than 1's and 2's (recall thatywill contain at least one 0!) and hencexy2zwill not belong toL1, which contradicts the Pumping lemma. (Actually this will be the case for anyk >1!)
ThereforeL1cannot be regular.
Observe that evenk= 0 would have help us showing that the language is not regular. Here however, the wordxy0z=xzwill contain less 0's than 1's and 2's. Stillxy0zwill not belong toL1, which would also contradict the Pumping lemma.
1.2L2=fw2 f0;1gj#1(w) = #0(w)gis not a Regular Language
Let us assume the languageL2is regular. Then the Pumping lemma for regular languages applies forL2.
Letnbe the constant given by the Pumping lemma.
2
Letw= 1n0n. Clearlyw2 L2andjwj>n.
By the lemma we know thatw=xyzwithjxyj6nandy6=.
Given our choice ofw, and given thatxyis located at the beginning of the word and that it is not longer thann, thenxyshould contain only 1's. Sincey6=thenyshould contain at least one 1 and sincexyshould contain only 1's thenywill also contain only 1's! Letx= 1jforj>0,y= 1ifori>1 (hencey6=!) andz= 1nji0n. That is, w= 1j1i1nji0n= 1n0nas expected. Then fork= 2, the wordxy2z=xyyz= 1j12i1nji0n= 1n+i0nwill contain more 1's than 0's sincen+i > nwheni>1. Hencexy2zwill not belong toL2, which contradicts the Pumping lemma. (Actually this will be the case for anyk >1!)
ThereforeL2cannot be regular.
Discussion note:In this exercise, we could have chosen for examplewto be the word (01) n. This word is also such thatw2 L2andjwj>n. Observe that this particular choice of word does not really allow us to continue rea- soning as desired. By the Pumpung lemma we know thatxybelongs to the rst half of the word (the length ofwis 2n) and we know thaty6=. But these two facts do not give enough information to have any meaningful reasoning arriving to a contradiction. Recall that we really do not know how the actual partsx,yandzlook like. It could perfectly be the case thatx=,y= 01 andz= (01)n1. Here, for anyk>0 we have thatxykz2 L2! So the choice of the word plays an important role when reasoning about the Pumping lemma for certain languages.
1.3L3=fwj#0(w)>2#1(w)gis not a Regular Language
Let us assume the languageL3is regular. Then the Pumping lemma for regular languages applies forL3.
Letnbe the constant given by the Pumping lemma.
Letw= 02n+11n. Clearlyw2 L3andjwj>n.
By the lemma we know thatw=xyzwithjxyj6nandy6=.
Given our choice ofw, and given thatxyis located at the beginning of the word and that it is not longer thann, thenxyshould contain only 0's. Sincey6=thenyshould contain at least one 0 and sincexyshould contain only 0's thenywill also contain only 0's! Then fork= 0, the wordxy0z=xzwill contain at most 2n0's (recall thaty6= so we are removing at least one 0 when we remove the party!) andn1's. Hence
0(w)62#1(w) and thenwwill not belong toL3, which contradicts the Pumping
lemma. (Observe that this is the only value ofkwhich allows us to arrive to a contradiction for this particular word!)
ThereforeL3cannot be regular.
2 Pumping Lemma for Context-Free Languages
The procedure is similar when we work with context-free languages. In order to show that a language is context-free we can give a context-free grammar that generates the language, a push-down automaton that recognises it, or use closure properties to show 3 that the language is context-free. But if we want to show that a language is NOT context- free, thePumping lemma for context-free languagesis a very useful tool. The lemma says: LetLbe a context-free language. Then, there exists a constantn|which depends onL|such that for everyw2 Lwithjwj>n, it is possible to break winto ve stringsx;u;y;vandzsuch thatw=xuyvzand
1.juyvj6n;
2.uv6=, that is, eitheruorvis not empty;
3.8k>0: xukyvkz2 L.
Here as well the lemma states certain things to happen whenever a language is context- free. The way we use the lemma is also similar to that in the previous section. If we want to prove that a languageLis not context-free we start by assuming it is, and then we reason using the information provided by the Pumping lemma (which must apply if indeed the language is context-free!) until we arrive to a contradiction. Since the only assumption we have made in the reasoning was that the languageLwas context-free, then this must the source of the problem and thus, we can conclude thatLis NOT context-free. An important dierence, however, is that we now have no information about where in the word the parts that can be \pumped" are located! The lemma tells us that given a wordwin the language which is longer than the constant provided by the lemma, the word can be divided into ve partsx;u;y;vandzsuch thatw=xuyvz. We know that uyvis not longer than the constant provided by the lemma but we do not know where in the wordwthe partuyvis located. So here we need to reason for ALL possible locations ofuyvwithin the wordw. So, if we want to prove thatLis not context-free we proceed as follows:
1. We assume thatLis context-free; hence the Pumping lemma for context-free lan-
guages must apply.
2. The Pumping lemma tells us that there must exist a constant depending onL; let
us give a name to this constant, sayn, so we can easily refer to it. Only now we can start using this constant!
3. Now we know that certain things must hold whenever we have a word in the language
which is longer than the constantn. Let us continue by picking a concrete wordw in the language which is larger thann. Observe that it needs to be clear that indeed jwj>n, otherwise this will need to be shown. In practice, since we do not really know the value ofn,wwill probably need to usenas part of its denition in order to actually guarantee thatjwj>n!
4. From the lemma we know that this wordwcan be split into ve partsx;u;y;v
andz. Observe that we do NOT know exactly how these parts look like, only that w=xuyvz,juyvj6nanduv6=, which is the information provided by the lemma! In particular, we do not know howxlooks like, and hence we do not know where exactlyuyvis placed within the word! 4
5. According to the Pumping lemma it must also be the case that for allk>0 then
xu kyvkz2 L. That is, if we \pump" the partsuandvas many times as we wish (but the same amount of times for both parts), then the wordxukyvkzmust still belong to the languageL. This means that if we nd at least ONE valuekfor which xu kyvkzdoes NOT belong toLfor ANY possible location ofuyvwithinw, then we arrive to a contradiction sincexukyvkzmust be inLfor ANYkand ANY location ofuyvwithinw! Observe however that the value ofkwhich makesxukyvkznot belonging toLdoes not need to be the same of each of the possible locations ofuyv withinw. Let us now look at the use of the Pumping lemma for context-free languages in more detail with the help of some examples.
2.1L1=f0i1i2iji>0gis not a Context-free Language
Let us assume the languageL1is context-free. Then the Pumping lemma for context-free languages applies forL1.
Letnbe the constant given by the Pumping lemma.
Letw= 0n1n2n. Clearlyw2 L1andjwj>n.
By the lemma we know thatw=xuyvzwithjuyvj6n. We know also thatuv6=, and hence we know that eitheruorvcould be empty but not both. Sincejuyvj6nthen we know that there is one numberp2 f0;1;2gthatdoes not occur inuyvand hence neither inuv. Sinceuv6=then we know that there is another numberq2 f0;1;2gthatdoesoccur inuv. Observe thatp6=qbecause a number cannot occur AND not occur inuvat the same time! Then the numberq(occurring inuv) has more occurrences than the numberp(not occurring inuv) inxu2yv2z, whateverqandpare. Hencexu2yv2zdoes not belong toL1.
ThereforeL1cannot be context-free.
2.2L4=faib2iciji >0gis not a Context-free Language
Let us assume the languageL4is context-free. Then the Pumping lemma for context-free languages applies forL4.
Letnbe the constant stated by the Pumping lemma.
Letw=anb2ncn. Clearlyw2 L4andjwj>n.
By the lemma we know thatw=xuyvzwithjuyvj6n. We know also thatuv6=, and hence we know that eitheruorvcould be empty but not both. We have ve dierent possibilities for the location ofuyvwithinw(recall we do not know where exactlyuyvis located in the word):
1.uyvconsists only ofa's: then for anyk >1 the wordxukyvkzwill have morea's
thanc's (becauseuv6=), and hence it will not belong toL4;
2.uyvconsists only ofb's: then for anyk >1 the wordxukyvkzwill have moreb's
thana's andc's together (again becauseuv6=), and hence it will not belong toL4;
3.uyvconsists only ofc's: then for anyk >1 the wordxukyvkzwill have morec's
thana's (becauseuv6=), and hence it will not belong toL4; 5
4.uyvconsists ofa's andb's: recall that we know thatuv6=but we do not really
know if bothuandvare non-empty. So, for anyk >1, when pumpinguandvwe could actually only be pumpinga's (ifuis not empty and contains onlya's, andv is empty), only pumpingb's (ifuis empty, andvis not empty and contains only b's), or we could be pumping botha's andb's (if neitherunorvare empty, and/or when at least one of them contains botha's andb's). We do know however that we are pumping at least oneaor oneb, and that we are not pumping anyc's. So we know thatxukyvkzwill not belong toL4because we would have morea's thanc's (whenever we pumpa's), or moreb's thana's andc's together (whenever we pump b'a but noa's). Observe that in the caseuand/orvcontain occurrences of botha's andb's,xukyvkzwill not even have the symbols in the right order whenk >1;
5.uyvconsists ofb's andc's: this is similar to the case before, only that for anyk >1
we will be pumping at least onebor onec, but we will not pump anya's. So we know thatxukyvkzwill not belong toL4because we would have morec's thana's (whenever we pumpc's), or moreb's thana's andc's together (whenever we pump b's but noc's). Even here, the order of the symbols inxukyvkzmight not be the right one if eitheruorvcontain occurrences of bothb's andc's whenk >1. So, for each of these ve possibilities there exists at least onekfor whichxukyvkzdoes not belong toL4. ThereforeL4cannot be context-free. Observe that in this example,uyvcannot consists ofa's,b's ANDc's. This is due to the fact thatjuyvj6nand also thatwhas 2nb's between thea's and thec's. Hence no part of the word containing at mostnsymbols could consists of all three letters.
2.3L5=fs2sjs2 f0;1ggis not a Context-free Language
Let us assume the languageL5is context-free. Then the Pumping lemma for context-free languages applies forL5.
Letnbe the constant given by the Pumping lemma.
Letw= 0n1n20n1n. Clearlyw2 L5andjwj>n.
By the lemma we know thatw=xuyvzwithjuyvj6n. We know also thatuv6=, and hence we know that eitheruorvcould be empty but not both. We have three dierent possibilities for the location ofuyvwithinw. Ifuyvtakes place completely before the 2, then fork= 0 and sinceuv6=, whatever part of the word is removed before the 2 will not be removed after the 2. Hencexukyvkz will not have the forms2sand therefore it will not belong toL5. We have a similar reasoning ifuyvtakes place completely after the 2. If 2 is part ofuyvthenuyvshould be of the form 1i20jfori;jsuch thati+j+16n. Even here, fork= 0 and sinceuv6=, the resulting word is not of the forms2seither because we remove the 2 (if 2 is part ofuv), or because we remove 1's (right before the
2) and/or we remove 0's (right after the 2) but we do not remove 1's at the end of the
word nor 0's at the beginning of the word. Hencexukyvkzwill not have the forms2sand therefore it will not belong toL5. So, for each of these three possibilitiesxu0yv0zdoes not belong toL5. ThereforeL5 cannot be context-free. 6quotesdbs_dbs17.pdfusesText_23
[PDF] More Applications of The Pumping Lemma