[PDF] 05 Nonregular Languages - CS:4330 Theory of Computation

View - Download 05 Nonregular Languages - CS:4330 Theory of Computation

Previous PDF

Next PDF

CS:4330 Theory of Computation

Spring 2018

Regular Languages

Nonregular Languages

Haniel Barbosa

Readings for this lecture

Chapter 1 of [Sipser 1996], 3rd edition. Section 1.4.

Nonregular languages

Consider the languageB=f0n1njn0g

BIf we attempt to find a DFA that recognizesBwe discover that such a machine needs to remember how many 0s have been seen so far as it reads the input BBecause the number of 0s isn"t limited, the machine needs to keep track of an unlimited number of possibilities BThis cannot be done with any finite number of states1 / 15

Intuition may fail us

BJust because a language appears to require unbounded memory in order to be recognized, it doesn"t mean that it is necessarily so

BExample

BL1=fwjwhas an equal number of 0s and 1sgis not regular BL2=fwjwhas an equal number of '01"s and '10"sgis regular2 / 15

Language nonregularity

BThe technique for proving nonregularity of some languages is provided by a theorem about regular languages calledpumping lemma BThe pumping lemma states that all regular languages have a special property BIf we can show that a language does not have this property we are guaranteed that it is not regular

3 / 15

Pumping property

All strings in the language can be "pumped" if they are at least as long as a certain special value, called thepumping length Meaning:each such string in the language contains a section that can be repeated any number of times with the resulting string remaining in the language

4 / 15

Pumping lemma

Theorem

IfAis a regular language, then there is a numberp(the pumping length) such that, ifsis any string inAof length at leastp, thensmay be divided intro three pieces,s=xyz, satisfying the conditions: (1) f oreach i0,xyiz2A (2)jyj>0 (3)jxyj p5 / 15

Proof idea

LetM= (Q;S; ;q0;F)be a DFA that recognizesA

BAssign a pumping lengthpto the number of states ofM BShow that any strings2A,jsj pmay be broken into three piecesxyz satisfying the pumping lemma"s conditions BNote that if there are no strings inAof length at leastpthen the theorem becomesvacuouslytrue, since all three conditions hold for all strings of length at leastpif there are no such strings6 / 15

Pumping lemma"s proof

LetM= (Q;S; ;q0;F)be a DFA recognizingAandpbe the number of states ofM. Lets=a1:::anbe a string overSwithnpandr1; :::;rn+1be the sequence of states while processings, i.e.ri+1=(ri;ai),1in Bn+1p+1and among the firstp+1elements inr1; :::;rn+1two must be the same state, sayrjandrk BSincerkoccurs among the firstp+1places in the sequence starting atr1, we havekp+1

BNow letx=a1:::aj1,y=aj:::ak1,z=ak:::an7 / 15

Note r n+1, which is an accept state, thereforeMmust acceptxyiz, fori0

BWe know thatj6=k, sojyj>0

BWe also know thatkp+1, sojxyj p

Thus, all conditions are satisfied and the lemma is proven.

8 / 15

Using the pumping lemma

Prove that a languageAis not regular using the pumping lemma: 1. Assume that Ais regular in order to obtain a contradiction 2. The pumping lemma guar anteesthe e xistenceof a pumping length psuch that all strings of lengthpor greater inAcan be pumped 3. Find s2A,jsj p, that cannot be pumped: demonstrate thatscannot be pumped by considering all ways of dividingsinto substringsx;y;z, showing that for each such division at least one of the conditions of the pumping lemma fails: a)xyiz62A, for somei0; or b)jyj 0; or c)jxyj>p9 / 15

Applications

Prove thatB=f0n1njn0gis not regularProof

Assume thatBis regular and letpbe the pumping length ofB. Choose s=0p1p2B; thereforej0p1pj>p. By pumping lemma,s=xyzsuch that for any i0,xyiz2BConsider the cases:

1.yconsists of0sonly. Then for somei,xyizhas more0sthan1sand is not in

B, violating condition(1).2.yconsists of1sonly. This leads to the same contraction.3.yconsists of0sand1s. Nowxyizmay have the same number of0sand1s

but they are out of order with some1sbefore some0s. Therefore it cannot be inBeither.The contraction is unavoidable if we make the assumption that B is regular, thereforeBis not regular.10 / 15

Applications

Prove thatB=f0n1njn0gis not regularProof

Assume thatBis regular and letpbe the pumping length ofB. Choose s=0p1p2B; thereforej0p1pj>p. By pumping lemma,s=xyzsuch that for any i0,xyiz2BConsider the cases:

1.yconsists of0sonly. Then for somei,xyizhas more0sthan1sand is not in

B, violating condition(1).2.yconsists of1sonly. This leads to the same contraction.3.yconsists of0sand1s. Nowxyizmay have the same number of0sand1s

but they are out of order with some1sbefore some0s. Therefore it cannot be inBeither.The contraction is unavoidable if we make the assumption that B is regular, thereforeBis not regular.10 / 15

Applications

Prove thatB=f0n1njn0gis not regularProof

Assume thatBis regular and letpbe the pumping length ofB. Choose s=0p1p2B; thereforej0p1pj>p. By pumping lemma,s=xyzsuch that for any i0,xyiz2BConsider the cases:

1.yconsists of0sonly. Then for somei,xyizhas more0sthan1sand is not in

B, violating condition(1).2.yconsists of1sonly. This leads to the same contraction.3.yconsists of0sand1s. Nowxyizmay have the same number of0sand1s

but they are out of order with some1sbefore some0s. Therefore it cannot be inBeither.The contraction is unavoidable if we make the assumption that B is regular, thereforeBis not regular.10 / 15

Applications

Prove thatB=f0n1njn0gis not regularProof

Assume thatBis regular and letpbe the pumping length ofB. Choose s=0p1p2B; thereforej0p1pj>p. By pumping lemma,s=xyzsuch that for any i0,xyiz2BConsider the cases:

1.yconsists of0sonly. Then for somei,xyizhas more0sthan1sand is not in

B, violating condition(1).2.yconsists of1sonly. This leads to the same contraction.3.yconsists of0sand1s. Nowxyizmay have the same number of0sand1s

but they are out of order with some1sbefore some0s. Therefore it cannot be inBeither.The contraction is unavoidable if we make the assumption that B is regular, thereforeBis not regular.10 / 15

Applications

Prove thatB=f0n1njn0gis not regularProof

Assume thatBis regular and letpbe the pumping length ofB. Choose s=0p1p2B; thereforej0p1pj>p. By pumping lemma,s=xyzsuch that for any i0,xyiz2BConsider the cases:

1.yconsists of0sonly. Then for somei,xyizhas more0sthan1sand is not in

B, violating condition(1).2.yconsists of1sonly. This leads to the same contraction.3.yconsists of0sand1s. Nowxyizmay have the same number of0sand1s

but they are out of order with some1sbefore some0s. Therefore it cannot be inBeither.The contraction is unavoidable if we make the assumption that B is regular, thereforeBis not regular.10 / 15

Applications

Prove thatB=f0n1njn0gis not regularProof

Assume thatBis regular and letpbe the pumping length ofB. Choose s=0p1p2B; thereforej0p1pj>p. By pumping lemma,s=xyzsuch that for any i0,xyiz2BConsider the cases:

1.yconsists of0sonly. Then for somei,xyizhas more0sthan1sand is not in

B, violating condition(1).2.yconsists of1sonly. This leads to the same contraction.3.yconsists of0sand1s. Nowxyizmay have the same number of0sand1s

but they are out of order with some1sbefore some0s. Therefore it cannot be inBeither.The contraction is unavoidable if we make the assumption that B is regular, thereforeBis not regular.10 / 15

Example

Prove thatC=fwjwhas an equal number of 0s and 1sgis not regularProof Assume thatCis regular andpis its pumping length. Lets=0p1p, hences2C. Then pumping lemma guarantees thats=xyz, wherexyiz2Cfor anyi0. If we take the divisionx=z=,y=0p1pit is the case thatxyiz2C, fori0.However: BCondition(3)states thatjxyj p, and in our casejyj>p. So0p1pcannot

be pumped.BIfjxyj p, thenymust consist of only0s.ITherefore there always is anis.t.xyiz62C, since there are more 0s

than 1s. This gives us the desired contradiction.Note that selectings= (01)pcould have misled us since this string can be

pumped by the division:x=,y=01,z= (01)p1. Thenxyiz2Cfor anyi0.11 / 15

Example

Prove thatC=fwjwhas an equal number of 0s and 1sgis not regularProof Assume thatCis regular andpis its pumping length. Lets=0p1p, hences2C. Then pumping lemma guarantees thats=xyz, wherexyiz2Cfor anyi0. If we take the divisionx=z=,y=0p1pit is the case thatxyiz2C, fori0.However: BCondition(3)states thatjxyj p, and in our casejyj>p. So0p1pcannot

be pumped.BIfjxyj p, thenymust consist of only0s.ITherefore there always is anis.t.xyiz62C, since there are more 0s

than 1s. This gives us the desired contradiction.Note that selectings= (01)pcould have misled us since this string can be

pumped by the division:x=,y=01,z= (01)p1. Thenxyiz2Cfor anyi0.11 / 15

Example

Prove thatC=fwjwhas an equal number of 0s and 1sgis not regularProof Assume thatCis regular andpis its pumping length. Lets=0p1p, hences2C. Then pumping lemma guarantees thats=xyz, wherexyiz2Cfor anyi0. If we take the divisionx=z=,y=0p1pit is the case thatxyiz2C, fori0.However: BCondition(3)states thatjxyj p, and in our casejyj>p. So0p1pcannot

be pumped.BIfjxyj p, thenymust consist of only0s.ITherefore there always is anis.t.xyiz62C, since there are more 0s

than 1s. This gives us the desired contradiction.Note that selectings= (01)pcould have misled us since this string can be

pumped by the division:x=,y=01,z= (01)p1. Thenxyiz2Cfor anyi0.11 / 15

Example

Prove thatC=fwjwhas an equal number of 0s and 1sgis not regularProof Assume thatCis regular andpis its pumping length. Lets=0p1p, hences2C. Then pumping lemma guarantees thats=xyz, wherexyiz2Cfor anyi0. If we take the divisionx=z=,y=0p1pit is the case thatxyiz2C, fori0.However: BCondition(3)states thatjxyj p, and in our casejyj>p. So0p1pcannot

be pumped.BIfjxyj p, thenymust consist of only0s.ITherefore there always is anis.t.xyiz62C, since there are more 0s

than 1s. This gives us the desired contradiction.Note that selectings= (01)pcould have misled us since this string can be

pumped by the division:x=,y=01,z= (01)p1. Thenxyiz2Cfor anyi0.11 / 15

Example

Prove thatC=fwjwhas an equal number of 0s and 1sgis not regularProof Assume thatCis regular andpis its pumping length. Lets=0p1p, hences2C. Then pumping lemma guarantees thats=xyz, wherexyiz2Cfor anyi0. If we take the divisionx=z=,y=0p1pit is the case thatxyiz2C, fori0.However: BCondition(3)states thatjxyj p, and in our casejyj>p. So0p1pcannot

be pumped.BIfjxyj p, thenymust consist of only0s.ITherefore there always is anis.t.xyiz62C, since there are more 0s

than 1s. This gives us the desired contradiction.Note that selectings= (01)pcould have misled us since this string can be

pumped by the division:x=,y=01,z= (01)p1. Thenxyiz2Cfor anyi0.11 / 15

An alternative method for the previous example

Exploit the properties of regular operations.

BIfC=fwjwhas an equal number of 0s and 1sgwere regular, then C\01would also be regular because01is regular and the intersection

of regular languages is also a regular languageBBut we know thatB=f0n1njn0gis not regularBSinceC\01=Bis not regular, thenCis not regular either.12 / 15

An alternative method for the previous example

Exploit the properties of regular operations.

BIfC=fwjwhas an equal number of 0s and 1sgwere regular, then C\01would also be regular because01is regular and the intersection

of regular languages is also a regular languageBBut we know thatB=f0n1njn0gis not regularBSinceC\01=Bis not regular, thenCis not regular either.12 / 15

An alternative method for the previous example

Exploit the properties of regular operations.

BIfC=fwjwhas an equal number of 0s and 1sgwere regular, then C\01would also be regular because01is regular and the intersection

of regular languages is also a regular languageBBut we know thatB=f0n1njn0gis not regularBSinceC\01=Bis not regular, thenCis not regular either.12 / 15

Another example

Prove thatF=fwwjw2 f0;1ggis nonregular using pumping lemmaProof idea Assume thatFis regular andpis its pumping length. Considers=0p10p12F.

Sincejsj>p, it can be divided into somes=xyzsatisfying the conditions.However, it is impossible to satisfy condition(3)unlessyconsists only of0s, and

this implies however thatxyyz62F, violating condition(1). ThereforeFis nonregular.Choosings=0p10p1as the candidate for a counterexample was crucial. Taking for example0p0pwould lead us no way, since it can be pumped.13 / 15

Another example

Prove thatF=fwwjw2 f0;1ggis nonregular using pumping lemmaProof idea Assume thatFis regular andpis its pumping length. Considers=0p10p12F.

Sincejsj>p, it can be divided into somes=xyzsatisfying the conditions.However, it is impossible to satisfy condition(3)unlessyconsists only of0s, and

this implies however thatxyyz62F, violating condition(1). ThereforeFis nonregular.Choosings=0p10p1as the candidate for a counterexample was crucial. Taking for example0p0pwould lead us no way, since it can be pumped.13 / 15

Another example

Prove thatF=fwwjw2 f0;1ggis nonregular using pumping lemmaProof idea Assume thatFis regular andpis its pumping length. Considers=0p10p12F.

Sincejsj>p, it can be divided into somes=xyzsatisfying the conditions.However, it is impossible to satisfy condition(3)unlessyconsists only of0s, and

this implies however thatxyyz62F, violating condition(1). ThereforeFis nonregular.Choosings=0p10p1as the candidate for a counterexample was crucial. Taking for example0p0pwould lead us no way, since it can be pumped.13 / 15

Pumping down

Sometimes "pumping down" is useful when apply the pumping lemma: BWe illustrate this using the pumping lemma to prove thatE=f0i1jji>jgis not regularBProof:by contradiction using pumping lemma. Assume thatEis regular and

its pumping length isp. Lets=0p+11p; from decomposition,s=xyz.BTo satisfy condition(3), i.e.jxyj p, thenyconsists only of 0s.BLet us examinexyyzto see if it is inE. Adding an extra-copy ofyincreases

thennumber of 0s. SinceEcontains all strings01that have more 0s than

1s, this will still give a string inE.14 / 15

Pumping down

Sometimes "pumping down" is useful when apply the pumping lemma: BWe illustrate this using the pumping lemma to prove thatE=f0i1jji>jgis not regularBProof:by contradiction using pumping lemma. Assume thatEis regular and

its pumping length isp. Lets=0p+11p; from decomposition,s=xyz.BTo satisfy condition(3), i.e.jxyj p, thenyconsists only of 0s.BLet us examinexyyzto see if it is inE. Adding an extra-copy ofyincreases

thennumber of 0s. SinceEcontains all strings01that have more 0s than

1s, this will still give a string inE.14 / 15

Pumping down

Sometimes "pumping down" is useful when apply the pumping lemma: BWe illustrate this using the pumping lemma to prove thatE=f0i1jji>jgis not regularBProof:by contradiction using pumping lemma. Assume thatEis regular and

its pumping length isp. Lets=0p+11p; from decomposition,s=xyz.BTo satisfy condition(3), i.e.jxyj p, thenyconsists only of 0s.BLet us examinexyyzto see if it is inE. Adding an extra-copy ofyincreases

thennumber of 0s. SinceEcontains all strings01that have more 0s than

1s, this will still give a string inE.14 / 15

Pumping down

Sometimes "pumping down" is useful when apply the pumping lemma: BWe illustrate this using the pumping lemma to prove thatE=f0i1jji>jgis not regularBProof:by contradiction using pumping lemma. Assume thatEis regular and

its pumping length isp. Lets=0p+11p; from decomposition,s=xyz.BTo satisfy condition(3), i.e.jxyj p, thenyconsists only of 0s.BLet us examinexyyzto see if it is inE. Adding an extra-copy ofyincreases

thennumber of 0s. SinceEcontains all strings01that have more 0s than

1s, this will still give a string inE.14 / 15

Try something else

BSincexyiz2Eeven wheni=0, consideri=0andxy0z=xz2E.

BThis decreases the number of0insBSinceshas just one more 0 than 1 andjyj 6=0, thenxycan have at most the

same number of0sand1s, which means thatxzcannot be inE. BThis provides us the required contradiction.15 / 15

Try something else

BSincexyiz2Eeven wheni=0, consideri=0andxy0z=xz2E.

BThis decreases the number of0insBSinceshas just one more 0 than 1 andjyj 6=0, thenxycan have at most the

same number of0sand1s, which means thatxzcannot be inE. BThis provides us the required contradiction.15 / 15quotesdbs_dbs20.pdfusesText_26

[PDF] pumping length of regular language

[PDF] purdue owl apa citation

[PDF] purdue owl pdf apa

[PDF] purdue owl pdf citation apa

[PDF] pure gym partners

[PDF] purebasic a beginner 's guide to computer programming

[PDF] puregym acquires fitness world

[PDF] puregym investor relations

[PDF] push ios updates airwatch

[PDF] pypacker

[PDF] python 3.6 cookbook

[PDF] python 3d data visualization

[PDF] python class best practices

[PDF] python cloud compiler

[PDF] python csv reader