Section: Properties of Context-freeLanguagesWhich of the following languages areCFL?• L={anbncj| 0 <n≤j}•L={anbjanbj| n>0,j >0}• L={anbjakbp| n + j ≤ k + p, n > 0,j >0,k >0,p>0}Pumping Lemma for RegularLanguage’s: Let L be a regularlanguage, Then there is a constant msuch that w ∈ L, |w|≥m,w=xyz suchthat• |xy|≤m•|y|≥1•for all i ≥ 0, xyiz ∈ L1Pumping Lemma for CFL’s Let L beany infinite CFL. Then there is aconstant m depending only on L,suchthat for every string w in L,with|w|≥m, we may partition w = uvxyzsuch that:|vxy|≤m, (limit on size of substring)|vy|≥1,(vand y not both empty)For all i ≥ 0, uvixyiz ∈L• Proof: (sketch) There is a CFG Gs.t. L=L(G).Consider the parse tree of a longstring in L.For any long string, somenonterminal N must appear twicein the path.2Example: ConsiderL = {anbncn: n ≥ 1}. Show L is not aCFL.• Proof: (by contradiction)Assume L is a CFL and apply thepumping lemma.Let m be the constant in thepumping lemma and considerw = ambmcm. Note |w|≥m.Show there is no division of w intouvxyz such that |vy|≥1,|vxy|≤m,and uvixyiz ∈Lfori=0,1,2,....3Thus, there is no breakdown of winto uvxyz such that |vy|≥1,|vxy|≤mand for all i ≥ 0, uvixyiz isin L. Contradiction, thus, L is not aCFL. Q.E.D.4Example Why would we want torecognize a language of the type{anbncn: n ≥ 1}?Example: ConsiderL = {anbncp: p>n>0}. Show L is notaCFL.•Proof: Assume L is a CFL andapply the pumping lemma. Let mbe the constant in the pumpinglemma and considerw =Note |w|≥m.Show there is no division of w intouvxyz such that |vy|≥1,|vxy|≤m,and uvixyiz ∈Lfori=0,1,2,....5Example: Consider L = {ajbk: k = j2}.Show L is not a CFL.• Proof: Assume L is a CFL andapply the pumping lemma. Let mbe the constant in the pumpinglemma and considerw =Show there is no division of w intouvxyz such that |vy|≥1,|vxy|≤m,and uvixyiz ∈Lfori=0,1,2,....Case 1: Neither v nor y can contain2 or more distinct symbols. If vcontains a’s and b’s, then uv2xy2z/∈Lsince there will be b’s before a’s.Thus, v and y can be only a’s, andb’s (not mixed).6Example: ConsiderL = {w ¯ww : w ∈ Σ∗}, Σ={a, b},where ¯wis the string w with each occurence ofa replaced by b and each occurence ofb replaced by a. Show L is not a CFL.• Proof: Assume L is a CFL andapply the pumping lemma. Let mbe the constant in the pumpinglemma and considerw =Show there is no division of w intouvxyz such that |vy|≥1,|vxy|≤m,and uvixyiz ∈Lfori=0,1,2,....7Example: Consider L = {anbpbpan}.Lis a CFL. The pumping lemma shouldapply!Let m ≥ 4 be the constant in thepumping lemma. Considerw = ambmbmam.We can break w into uvxyz, with:8Chap 8.2 Closure Properties of CFL’sTheorem CFL’s are closed underunion, concatenation, andstar-closure.• Proof:Given 2 CFG G1=(V1,T1,S1,P1) andG2=(V2,T2,S2,P2)– Union:Construct G3s.t. L(G3)=L(G1)∪L(G2).G3=(V3,T3,S3,P3)9– Concatenation:Construct G3s.t. L(G3)=L(G1)◦L(G2).G3=(V3,T3,S3,P3)– Star-ClosureConstruct G3s.t. L(G3)=L(G1)∗G3=(V3,T3,S3,P3)10Theorem CFL’s are NOT closed underintersection and complementation.• Proof:– Intersection:11– Complementation:12Theorem: CFL’s are closed underregular intersection. If L1is CFL andL2is regular, then L1∩ L2is CFL.• Proof: (sketch) We take a NPDAfor L1and a DFA for L2andconstruct a NPDA for L1∩ L2.M1=(Q1,Σ,Γ,δ1,q0,z,F1) is anNPDA such that L(M1)=L1.M2=(Q2,Σ,δ2,q00,F2) is a DFA suchthat L(M2)=L2.Example of replacing arcs (NOT aProof!):13We must formally define δ3.IfthenMust showif and only if14Questions about CFL:1. Decide if CFL is empty?2. Decide if CFL is infinite?15Example: ConsiderL = {a2nb2mcndm: n, m ≥ 0}. Show L isnot a CFL.• Proof: Assume L is a CFL andapply the pumping lemma. Let mbe the constant in the pumpinglemma and considerw = a2mb2mcmdm.Show there is no division of w intouvxyz such that |vy|≥1,|vxy|≤m,and uvixyiz ∈Lfori=0,1,2,....Case 1: Neither v nor y can contain2 or more distinct symbols. If vcontains a’s and b’s, then uv2xy2z/∈Lsince there will be b’s before a’s.Thus, v and y can be only a’s, b’s,c’s, or d’s (not mixed).Case 2: v = at1, then y = at2or bt3(|vxy|≤m)If y = at2, then16uv2xy2z = a2m+t1+t2b2mcmdm/∈ L sincet1+ t2> 0, the number of a’s is nottwice the number of c’s.If y = bt3, thenuv2xy2z = a2m+t1b2m+t3cmdm/∈ L sincet1+ t3> 0, either the number of a’s(denoted n(a)) is not twice n(c)orn(b) is not twice n(d).Case 3: v = bt1, then y = bt2or ct3If y = bt2, thenuv2xy2z = a2mb2m+t1+t2cmdm/∈ L sincet1+ t2> 0,n(b)>2∗n(d).If y = ct3, thenuv2xy2z = a2mb2m+t1cm+t3dm/∈ L sincet1+ t3> 0, either n(b)> 2∗n(d)or2∗n(c)>n(a).Case 4: v = ct1, then y = ct2or dt3If y = ct2, thenuv2xy2z = a2mb2mcm+t1+t2dm/∈ L sincet1+ t2> 0, 2∗n(c)>n(a).17If y = dt3, thenuv2xy2z = a2mb2mcm+t1dm+t3/∈ L sincet1+ t3> 0, either 2∗n(c)>n(a)or2∗n(d)>n(b).Case 5: v = dt1, then y = dt2then uv2xy2z = a2mb2mcmdm+t1+t2/∈ Lsince t1+ t2> 0, 2∗n(d)>n(c).Thus, there is no breakdown of winto uvxyz such that |vy|≥1,|vxy|≤mand for all i ≥ 0, uvixyiz isin L. Contradiction, thus, L is not aCFL.