Theorem$[$PumpingLemmaforRegularLanguages$]$:IfLisaregularlanguage,thenthereisapositiveintegerpsuchthatforeverystringsinLoflengthatleastp,therearestringsx,y$,$andzsatisfyingthefollowing:$1.$s$=$xyz$2.|$xy$|<=$p$3.|$y$|>04.$foreveryi in N$,$xyiz in L

Theorem$[$PumpingLemmaforRegularLanguages$,$contrapositive$]$:LanguageLisnotregularifthefollowingholds:foreverypositiveintegerp,thereisastringsinLoflengthatleastpsuchthatforallstringsx,y$,$andzwiths$=$xyzand$|$xy$|<=$p$,$and$|$y$|>0,$thereisani in Nsuchthatxyiz$$L$.$Theoperativestatementherehasfournestedquantifiers:Foreverypositiveintegerp,thereisastringsinLoflengthatleastpsuchthatforallstringsx,y$,$andzwiths$=$xyz$,|$xy$|<=$p$,$and$|$y$|>0,$thereisani in Nsuchthatxyiz$$L$.$GivenalanguageL,considerthefollowing$2-$playergame:$1.$player$1$picksapositiveintegerp$2.$player$2$picksastringsinLoflengthatleastp$3.$Player$1$picksstringsx,y$,$andzwiths$=$xyz$,|$xy$|<=$p$,$and$|$y$|>0,4.$Player$2$picksi in N$5.$Player$2$winsifxyiz$$L$.$Otherwise,Player$1$wins.ThepumpinglemmacanbeinterpretedtosaythatPlayer$2$willhaveawinningstrategyforthisgameifandonlyifLisnotregular.Forexample,letLbethelanguageofallstringsofa'sandb'sthatarepalindromes$($i$.$e$.,$thesameforwardasbackward$).$Player$2$'sstrategyis:$$InStep$2,$chooseastringofalla'soflengthp,followedbyastringofb'soflengthp,followedagainbyastringofpa's.$$Instep$4,$choosei$=2.$

ExerciseSet$3$:In$1-6,$ifthelanguageisregular,writeeitheraregularexpressionoradeterministicFSMforit.Ifitisnotregular,giveawinningstrategyforPlayer$2$inthe"pumpinglemmagame"$\mathrm{.}1.$LetLbethelanguageofallstringsofthecharacters'$(\text{'}$and$\text{'})\text{'}$thatarebalancedparentheses$\mathrm{.}2.$LetLbethelanguageofallstringsofa'sandb'swithmorea'sthanb's$\mathrm{.}3.$LetLbethelanguageofallstringsofa'sandb'sthathaveatleast$2$a'sandatleast$2$b$\text{'}$s$\mathrm{.}4.$LetLbethelanguageofallstringsofa'sandb'sthatendwithbb$\mathrm{.}5.$LetLbethelanguageofallstringsofa'sandb'sthatconsistofsomenumberofa'sfollowedbythesamenumberofb's$\mathrm{.}6.$LetLbethelanguageofallstringsofa'sandb'sinwhichthesequenceaboccursatleastonce$\mathrm{.}7.$Beabletostatethepumpinglemmaforregularlanguages.Additionally,exercises$2\mathrm{.}20-2\mathrm{.}25$fromchapter$2$areassigned.