唐常杰翻译的计算理论导引5(共65张PPT)

LectureNotes

forComputationTheoryBook:《计算理论导引》IntroductiontotheTheoryofComputationSection2.2-2.3PDA–CFLProf:唐常杰

Http:///~chjtangStudents:PhdMSinCS.2000--2006,SCUStyle:Lecture/Seminar2023/5/161第1页，共65页。今天课程Chapter2:2.2(Pushdownautomata)2.3Non-CFlanguages2.3CFLpumpinglemmaClosurepropertiesofCFL2023/5/162第2页，共65页。

2023/5/163第3页，共65页。2.2PushdownAutomata,ep101,cp69Pushdownautomataareforcontext-free

languageswhatfiniteautomataareforregular

languages.PDA:描述CFL的设备PDAsarerecognizingautomatathathavea

singlestack(=memory):“硬件”增加了栈

Last-InFirst-Outpushingandpopping对应于可用if，goto,读，和栈操作的C程序Difference:PDAsareinherentlynondeterministic.

(Theyarenotpracticalmachines.)天生不确定2023/5/164第4页，共65页。2.2PushdownAutomata,ep101,cp69Pushdownautomataareforcontext-free

languageswhatfiniteautomataareforregular

languages.PDA:描述CFL的设备PDAsarerecognizingautomatathathavea

singlestack(=memory):“硬件”增加了栈

Last-InFirst-Outpushing

andpopping对应于可用if，goto,读，和栈操作的C程序Difference:PDAsareinherentlynondeterministic.

(Theyarenotpracticalmachines.)天生不确定2023/5/165第5页，共65页。2.2PushdownAutomata,ep101,cp69Pushdownautomataareforcontext-free

languageswhatfiniteautomataareforregular

languages.PDA:描述CFL的设备PDAsarerecognizingautomatathathavea

singlestack(=memory):“硬件”增加了栈

Last-InFirst-Outpushing

andpopping对应于可用if，goto,读，和栈操作的C程序Difference:PDAsareinherentlynondeterministic.

(Theyarenotpracticalmachines.)天生不确定2023/5/166第6页，共65页。InformalDescriptionPDA(1)

与ep102，cp69图稍有不同,实质一样内部状态集合StatesetQxyyzxstackThePDAM读带w

and且作栈操作.Dependingon

-inputwi

,输入字母表

-stacksj,栈字母表

-stateqkQ状态集合

thePDAM:-jumpstoanewstate,

-pushesanelement

(nondeterministically)2023/5/167第7页，共65页。InformalDescriptionPDA(2)ep102internalstate

setQxyyzxstackAfterthePDAhas

readcompleteinput,

MwillbeinstateQ当读完W且进入终止态，则接受w,栈用来作简单记忆历史和对比，只是栈顶元素可见，能力有限，且不灵活Ifpossibletoendin

acceptingstateFQ,

thenMacceptsw2023/5/168第8页，共65页。InformalDescriptionPDA(2)ep102internalstate

setQxyyzxstackAfterthePDAhas

readcompleteinput,

MwillbeinstateQ当读完W且进入终止态，则接受w,栈用来作简单记忆历史和对比，只是栈顶元素可见，能力有限，且不灵活Ifpossibletoendin

acceptingstateFQ,

thenMacceptsw2023/5/169第9页，共65页。InformalDescriptionPDA(1)

与ep102，cp6９

图稍有不同内部状态集合StatesetQxyyzxstackThePDAM读带w

and且作栈操作.Dependingon

-inputwi

,输入字母表

-stacksj,栈字母表

-stateqkQ状态集合

thePDAM:-jumpstoanewstate,

-pushesanelement

(nondeterministically)2023/5/1610第10页，共65页。FormalDescriptionPDA定义2.8ep103

形式化定义cp70APushdownAutomataMisdefinedbya

sixtuple(Q,,,,q0,F),withQfinitesetofstates有限个状态（寄存器）

finiteinputalphabet字母表finitestackalphabet可压栈字符表

q0startstateQFsetofacceptingstatesQ接受态transitionfunction状态转移函数~相当于3种语句goto,push,pop:QP(Q)2023/5/1611第11页，共65页。FormalDescriptionPDA定义2.8ep103

形式化定义cp67APushdownAutomataMisdefinedbya

sixtuple(Q,,,,q0,F),withQfinitesetofstates有限个状态（寄存器）

finiteinputalphabet字母表finitestackalphabet可压栈字符表q0startstateQFsetofacceptingstatesQ接受态transitionfunction状态转移函数~相当于3种语句goto,push,pop:QP(Q)2023/5/1612第12页，共65页。PDAforL={0n1n|n0}ep104cp67例c3.9Examplee2.9c3.9:背景检查左右括号(0,1)是否配对

ThePDAfirstpushes“$0n”onstack.$栈底符号，压箱钱，表示后来压入栈的存款用完了。Then,whilereadingthe1nstring,thezerosarepoppedagain.栈顶对比，左右括号配对，则同归于尽，If,intheend,$isleftonstack,then“accept”下页释图q1q3q2q4,$,$1,01,00,02023/5/1613第13页，共65页。PDAforL={0n1n|n0}ep104cp71例2.9Example2.9:背景检查左右括号(0,1)是否配对

ThePDAfirstpushes“$0n”onstack.$栈底符号，压箱钱，表示后来压入栈的存款用完了。Then,whilereadingthe1nstring,thezerosarepoppedagain.栈顶对比，左右括号配对，则同归于尽，If,intheend,$isleftonstack,then“accept”下页释图q1q3q2q4,$,$1,01,00,02023/5/1614第14页，共65页。PDAforL={0n1n|n0}ep104cp71例2.9

0-—左括号，1—右括号q1读，栈顶变箱底钱q2遇左括号0，压0栈入栈q1q3q2q4,$,$1,01,00,0，弹出压箱钱，栈空

在q3,遇右括号1，弹出左括号，1，0兑消在q2遇1，弹出0,兑消绿框表示栈顶字符变化2023/5/1615第15页，共65页。MachineDiagramfor0n1nep103cp71例2.9q1q3q2q4,$,$1,01,00,0例接受

w=000111(state;stack)evolution:(q1;)(q2;$)(q2;0$)(q2;00$)(q2;000$)(q3;00$)(q3;0$)(q3;$)(q4;)Thisfinalq4isanacceptingstate练习，手写跟踪这一例题状态栈内值2023/5/1616第16页，共65页。MachineDiagramfor0n1ncp71q1q3q2q4,$,$1,01,00,0例拒绝w=0101(state;stack)evolution:(q1;)(q2;$)(q2;0$)(q3;$)(q4;)…Butwestillhavepartofinput“01”.Thereisnoacceptingpath.理解为用括号配对比较直观状态栈内值2023/5/1617第17页，共65页。PDAsversusCFLep106，cp72，计划自学内容Theorem2.12:AlanguageLiscontext-free

ifandonlyifthereisapushdownautomataM

thatrecognizesL.L是CFLL被PDA接受Twostepproof:1)GivenaCFGG,constructaPDAMG部分2)GivenaPDAM,makeaCFGGM部分若干教材都说可以证明而略去证明，此书的证明适合静心自学，不适合课堂讲解或者承认结论，读第二遍时再深入理解2023/5/1618第18页，共65页。PDAsversusCFLep106，cp72，计划自学内容Theorem２.12:AlanguageLiscontext-free

ifandonlyifthereisapushdownautomataM

thatrecognizesL.L是CFLL被PDA接受Twostepproof:1)GivenaCFGG,constructaPDAMG部分2)GivenaPDAM,makeaCFGGM部分若干教材都说可以证明而略去证明，此书的证明适合静心自学，不适合课堂讲解或者承认结论，读第二遍时再深入理解2023/5/1619第19页，共65页。PDAsversusCFLep106，cp72，计划自学内容Theorem２.12:AlanguageLiscontext-free

ifandonlyifthereisapushdownautomataM

thatrecognizesL.L是CFLL被PDA接受Twostepproof:1)引理２.１３

GivenaCFGG,constructaPDAMG部分2)引理２.１5

GivenaPDAM,makeaCFGGM部分若干教材都说此定理容易证明但又略去证明，此定理的证明适合静心自学，不适合课堂讲解。可以先承认结论，读第二遍时再深入理解,或者征求同学志愿发言来讲解（证明在下页）2023/5/1620第20页，共65页。引理2.13

的证明（１）拟略去或供同学发言用

引理2.13

如果一个语言是上下文无关的，则存在一台下推自动机识别它。

证明思路设A是CFL，根据定义，存在一个CFGG产生它。说明如何把G转换成一台等价的PDAP。确定是否存在关于输入w的派生PDAP当G产生w时，接受这个输入。派生是当文法产生一个字符串时的替换序列，派生的每一步产生一个变元和终结符的中间字符串。设计P，以确定是否有一系列使用G的规则替换，能够从起始变元导出w检验是否有关于w的派生。困难在于判断要替换，PDA的非确定性使得它能够猜想出正确的替换序列，在派生的每一步，非确定地选择关于某个变元的一条规则，并且对这个变元做替换。2023/5/1621第21页，共65页。引理2.13

的证明（２）拟略去或供同学发言用为简化工作，对P作修改，使其具有以下三个特点。

1）有唯一的接受状态qaccept。

2）在接受之前清空栈。

3）每一个转移把一个符号推入栈(推入动作)，或者把一个符号弹出栈(弹出动作)，但不同时做这两个动作。使P具有特点1和2较容易，使P具有特点3就要把每一个同时弹出和推入的转移替换成两个转移，中间要经过一个新的状态；把每一个既不弹出也不推入的转移替换成两个转移，先推入任意一个栈符号，然后再把它弹出。2023/5/1622第22页，共65页。引理2.15的证明（１）拟略去或供同学发言用

引理2.15

如果一个语言被一台下推自动机识别，则它是上下文无关的。

证明思路现有一台PDAP，要构造一个CFGG，它产生P接受的所有字符串。换言之，如果一个字符串能使P从它的起始状态转移到一个接受状态，则G应该产生这个字符串。为了获得这个结果，我们设计一个能做更多事情的文法。对于P的每一对状态p和q，文法有一个变元Apq。它产生所有能够把P从p和空栈一块带到q和空栈的字符串。可以看出不管栈的内容是什么，这样的字符串也能够把P从p带到q，并且保持栈的内容在状态q和在状态p时—样。

2023/5/1623第23页，共65页。引理2.1５

证明（２）拟略去或供同学发言用为简化，对P作轻微修改，具有下三特点。

1）有唯一的接受状态qaccept。

2）在接受之前清空栈。

3）每一个转移把一个符号推入栈(推入动作)，或者把一个符号弹出栈(弹出动作)，但不同时做这两个动作。使P具有特点1和2较容易，使P具有特点3就要把每一个同时弹出和推入的转移替换成两个转移，中间要经过一个新的状态；把每一个既不弹出也不推入的转移替换成两个转移，先推入任意一个栈符号，然后再把它弹出。

2023/5/1624第24页，共65页。引理2.1５

证明（２）拟略去或供同学发言用设计G，使得Apq产生把P从p带到q并且以空栈开始和结束的所有字符串，了解P对这样的字符串如何运行。对于任一的字符串x，P的每—个动作是推入或是弹出，但对空栈不能弹出，对x的第一个动作一定是推入。因结束时栈空，对x的最后一个动作一定是弹出。在P对x的计算过程两情况：仅在开始和结束时，栈是空的；或者除开始和结束时之外，在计算中的某个地方，栈变成空的。如是前情况，最后弹出的符号一定就是开始时推入的那个符号。用规则Apq→aArsb模拟前一种情况，其中a是在做第一个动作时读的输入符号，b是在做最后一个动作时读的输入符号，r是跟在p后面的状态，s是q的前一个状态。用规则Apq→AprArq模拟后一种情况，其中r是栈在计算中间变成空的时候的状态。2023/5/1625第25页，共65页。2.3Non-CFLanguagesep115cp7６

先讲思想ThelanguageL={anbncn|n0}doesnot

appeartobecontext-free.这个语言不是CFL证明此事需要新的泵定理（言多必重复）

Informal:Theproblemisthateveryvariable

can(only)act‘byitself’(context-free).比喻：前后文无关的人格，我行我素，不受舆论左右，两岸猿声啼不住，轻舟已过万重山，则某些爱好和行为就会重复TheproblemofA*vAy:

IfS*uAz*uvAyz*uvxyzL,thenS*uAz*uvAyz*…*uviAyiz

*uvixyizLaswell,foralli=0,1,2,…2023/5/1626第26页，共65页。2.3Non-CFLanguagesep115cp7７

先讲思想ThelanguageL={anbncn|n0}doesnot

appeartobecontext-free.这个语言不是CFL证明此事需要新的泵定理（言多必重复）Informal:Theproblemisthateveryvariable

can(only)act‘byitself’(context-free).比喻：前后文无关的人格，我行我素，不受舆论左右，两岸猿声啼不住，轻舟已过万重山，则某些爱好和行为就会重复TheproblemofA*vAy:

IfS*uAz*uvAyz*uvxyzL,thenS*uAz*uvAyz*…*uviAyiz

*uvixyizLaswell,foralli=0,1,2,…2023/5/1627第27页，共65页。2.3Non-CFLanguagesep115cp7７

先讲思想ThelanguageL={anbncn|n0}doesnot

appeartobecontext-free.这个语言不是CFL证明此事需要新的泵定理（言多必重复）Informal:Theproblemisthateveryvariable

can(only)act‘byitself’(context-free).比喻：前后文无关的人格，我行我素，不受舆论左右，两岸猿声啼不住，轻舟已过万重山，则某些爱好和行为就会重复TheproblemofA*vAy:

IfS*uAz*uvAyz*uvxyzL,thenS*uAz*uvAyz*…*uviAyiz

*uvixyizLaswell,foralli=0,1,2,…2023/5/1628第28页，共65页。“PumpingLemma２.19forCFLs”

ep115与RL不同，CFL两处打圈，至少一处是真圈，先讲思想Idea:Ifwecanprovetheexistenceofderivations

forelementsoftheCFLLthatusethestepA*vAy,thenanewformof‘v-ypumping’holds:A*vAy*v2Ay2*v3Ay3*…)要点：证明存在如上的“中递归”派生，反复调用Observation:Wecanprovethisexistenceif

theparse-treeistallenough.当派生树足够高，用尽了资源，就会出现重复2023/5/1629第29页，共65页。“PumpingLemma２.19forCFLs”

cp77

与RL不同，CFL两处打圈，至少一处是真圈，先讲思想Idea:Ifwecanprovetheexistenceofderivations

forelementsoftheCFLLthatusethestepA*vAy,thenanewformof‘v-ypumping’holds:A*vAy*v2Ay2*v3Ay3*…)要点：证明存在如上的“中递归”派生，反复调用Observation:Wecanprovethisexistenceif

theparse-treeistallenough.当派生树足够高，用尽了资源，就会出现重复2023/5/1630第30页，共65页。RememberParseTreesep116cp75，先讲思想ParsetreeforSAbbcBa*cbbccccaBca

cbbccccacca当树足够高时，有限的变量符就会被重复使用SbbacAcccaAcccBB2023/5/1631第31页，共65页。PumpingaParseTreecp77，先讲思想AAuvxyzIfs=uvxyzLislong,thenitsparse-treeistall.

Hence,thereisapathonwhichavariableA

repeatsitself.WecanpumpthisA–Apart.S路径高度超过变量个数时，至少一个变量符号被重复2023/5/1632第32页，共65页。ATreeTallEnoughep116cp77，先讲思想LetLbeacontext-freelanguage,andlet

Gbeitsgrammarwithmaximalbsymbols

ontherightsideoftherules:AX1…XbAparsetreeofdepthhproducesastring

withmaximumlengthofbh.

Longstringsimpliestalltrees.

Let|V|bethenumberofvariablesofG.

Ifh=|V|+2orbigger,thenthereisavariableon

a‘top-downpath’thatoccursmorethanonce.变量个数V树高h=v+2时2023/5/1633第33页，共65页。ATreeTallEnoughep116cp77，先讲思想LetLbeacontext-freelanguage,andlet

Gbeitsgrammarwithmaximalbsymbols

ontherightsideoftherules:AX1…XbAparsetreeofdepthhproducesastring

withmaximumlengthofbh.

Longstringsimpliestalltrees.

Let|V|bethenumberofvariablesofG.

Ifh=|V|+2orbigger,thenthereisavariableon

a‘top-downpath’thatoccursmorethanonce.变量个数V树高h=v+2时2023/5/1634第34页，共65页。ATreeTallEnoughep116cp77，先讲思想LetLbeacontext-freelanguage,andlet

Gbeitsgrammarwithmaximalbsymbols

ontherightsideoftherules:AX1…XbAparsetreeofdepthhproducesastring

withmaximumlengthofbh.

Longstringsimpliestalltrees.

Let|V|bethenumberofvariablesofG.

Ifh=|V|+2orbigger,thenthereisavariableon

a‘top-downpath’thatoccursmorethanonce.变量个数V树高h=v+2时2023/5/1635第35页，共65页。uvxyzL派生树足够高，分段记号,ep116cp77AAuvxyzByrepeatingtheA–Apartweget…S期待的中递归2023/5/1636第36页，共65页。uv2xy2zL,i=2

ep116在上页基础上A再自己派生一次，先讲思想AuvxyzRAAvxy…whileremovingtheA–-Agives…S2023/5/1637第37页，共65页。uxzL,i=0,ep116cp=77，先讲思想AuzIngeneraluvixyizLforalli=0,1,2,…Sx2023/5/1638第38页，共65页。PumpingLemmaforCFL形式化的表述

ThmC3.19

ep115,cp77用言多必复概括Foreverycontext-freelanguageL,thereisa

pumpinglengthp,suchthatforeverystring

sLand|s|p,wecanwrites=uvxyzwith

1)uvixyizLforeveryi{0,1,2,…}//两处打圈

2)|vy|1//真圈

3)|vxy|p//扇出度小于泵长（变量未重复，不超过变量个数）Notethat1)impliesthatuxzL

2)saysthatvycannotbetheemptystring

Condition3)isnotalwaysused2023/5/1639第39页，共65页。PumpingLemmaforCFL形式化的表述

ThmC3.19

ep115,cp75用言多必复概括Foreverycontext-freelanguageL,thereisa

pumpinglengthp,suchthatforeverystring

sLand|s|p,wecanwrites=uvxyzwith

1)uvixyizLforeveryi{0,1,2,…}//两处打圈

2)|vy|1//真圈

3)|vxy|p//扇出度小于泵长（变量未重复，不超过变量个数）Notethat1)impliesthatuxzL

2)saysthatvycannotbetheemptystring

Condition3)isnotalwaysused2023/5/1640第40页，共65页。FormalProofofPumpingLemmaep116

严格证明LetG=(V,,R,S)bethegrammarofaCFL.

Maximumsizeofrulesisb2:AX1…XbAstringsrequiresaminimumtree-depthlogb|s|.If|s|p=b|V|+2,thentree-depth|V|+2,hence

thereisapathandvariableAwhereArepeats

itself:S*uAz*uvAyz*uvxyzItfollowsthatuvixyizLforalli=0,1,2,…Furthermore:

|vy|1becausetreeisminimal

|vxy|pbecausebottomtreewithpleaves

hasno‘repeatingpath’2023/5/1641第41页，共65页。FormalProofofPumpingLemmaep116

严格证明LetG=(V,,R,S)bethegrammarofaCFL.

Maximumsizeofrulesisb2:AX1…XbAstringsrequiresaminimumtree-depthlogb|s|.If|s|p=b|V|+2,thentree-depth|V|+2,hence

thereisapathandvariableAwhereArepeats

itself:S*uAz*uvAyz*uvxyzItfollowsthatuvixyizLforalli=0,1,2,…Furthermore:

|vy|1becausetreeisminimal

|vxy|pbecausebottomtreewithpleaves

hasno‘repeatingpath’2023/5/1642第42页，共65页。求证anbncn非CFL

(Ex.2.20)ep117cp78反证法AssumethatB={anbncn|n0}isCFLLetpbethepumpinglength,ands=apbpcpBP.L.:s=uvxyz=apbpcp,withuvixyizBforalli0Optionsfor|vxy|:只有下列情况1)Thestringsvandyareuniform

(v=a…aandy=c…c,forexample).

Thenuv2xy2zwillnotcontainthesamenumber

ofa’s,b’sandc’s,henceuv2xy2zB2)vandyarenotuniform.

Thenuv2xy2zwillnotbea…ab…bc…c

Henceuv2xy2zB2023/5/1643第43页，共65页。求证anbncn非CFL

(Ex.2.20)ep117cp78反证法AssumethatB={anbncn|n0}isCFLLetpbethepumpinglength,ands=apbpcpBP.L.:s=uvxyz=apbpcp,withuvixyizBforalli0Optionsfor|vxy|:只有下列情况1)Thestringsvandyareuniform

(v=a…aandy=c…c,forexample).

Thenuv2xy2zwillnotcontainthesamenumber

ofa’s,b’sandc’s,henceuv2xy2zB2)vandyarenotuniform.

Thenuv2xy2zwillnotbea…ab…bc…c

Henceuv2xy2zB2023/5/1644第44页，共65页。求证anbncn非CFL

(Ex.2.20)ep117cp78反证法AssumethatB={anbncn|n0}isCFLLetpbethepumpinglength,ands=apbpcpBP.L.:s=uvxyz=apbpcp,withuvixyizBforalli0Optionsfor|vxy|:只有下列情况1)Thestringsvandyareuniform

(v=a…aandy=c…c,forexample).

Thenuv2xy2zwillnotcontainthesamenumber

ofa’s,b’sandc’s,henceuv2xy2zB2)vandyarenotuniform.

Thenuv2xy2zwillnotbea…ab…bc…c

Henceuv2xy2zB2023/5/1645第45页，共65页。Pumpinganbncn(Ex2.21.)

ep117cp78小结上页：AssumethatB={anbncn|n0}isCFL

Letpbethepumpinglength,ands=apbpcpB

P.L.:s=uvxyz=apbpcp,withuvixyizBforalli0Weshowed:Nooptionsfor|vxy|suchthat

uvixyizBforalli.Contradiction.Bisnotacontext-freelanguage.DFA小学生，NDFA初中生PDA高中生，TM大学生2023/5/1646第46页，共65页。Pumpinganbncn(Ex2.21.)

ep117cp78小结上页：AssumethatB={anbncn|n0}isCFL

Letpbethepumpinglength,ands=apbpcpB

P.L.:s=uvxyz=apbpcp,withuvixyizBforalli0Weshowed:Nooptionsfor|vxy|suchthat

uvixyizBforalli.Contradiction.Bisnotacontext-freelanguage.DFA小学生，NDFA初中生PDA高中生，TM大学生2023/5/1647第47页，共65页。理解为用括号配对比较直观这个语言不是CFL证明此事需要新的泵定理（言多必重复）Bisnotacontext-freelanguage.FormalDescriptionPDA定义2.CarefullytakethestringssD.1)Thestringsvandyareuniform

(v=a…aandy=c…c,forexample).Dependingon

-inputwi,输入字母表

-stacksj,栈字母表

-stateqkQ状态集合

thePDAM:APushdownAutomataMisdefinedbya

sixtuple(Q,,,,q0,F),withDifference:PDAsareinherentlynondeterministic.Pushdownautomataareforcontext-free

languageswhatfiniteautomataareforregular

languages.PDAforL={0n1n|n0}ep104cp67例c3.Twooptionsfor1|vxy|p:只有2种可能，分别讨论$栈底符号，压箱钱，表示后来压入栈的存款用完了。说明如何把G转换成一台等价的PDAP。Astringsrequiresaminimumtree-depthlogb|s|.Example2.21(Pumpingdown)ep118cp78求证thatC={aibjck|0ijk}isnotcontext-free.Proof

Letpbethepumpinglength,ands=apbpcpC

P.L.:s=uvxyz,suchthatuvixyizCforeveryi0Twooptionsfor1|vxy|p:只有2种可能，分别讨论1)vxy=a*b*,thenthestringuv2xy2zhasnotenoughc’s,henceuv2xy2zC//在前面打圈，c的个数少2)vxy=b*c*,thenthestringuv0xy0z=uxz

hastoomanya’s,henceuv0xy0zCContradiction:Cisnotacontext-freelanguage.窍门：abc分段集中，且个数递增，用打圈破坏个数相等。第一步类似平面几何题的辅助线，神出鬼没，较难，2023/5/1648第48页，共65页。Example2.21(Pumpingdown)ep118cp78求证thatC={aibjck|0ijk}isnotcontext-free.Proof

Letpbethepumpinglength,ands=apbpcpC

P.L.:s=uvxyz,suchthatuvixyizCforeveryi0Twooptionsfor1|vxy|p:只有2种可能，分别讨论1)vxy=a*b*,thenthestringuv2xy2zhasnotenoughc’s,henceuv2xy2zC//在前面打圈，c的个数少2)vxy=b*c*,thenthestringuv0xy0z=uxz

hastoomanya’s,henceuv0xy0zCContradiction:Cisnotacontext-freelanguage.窍门：abc分段集中，且个数递增，用打圈破坏个数相等。第一步类似平面几何题的辅助线，神出鬼没，较难，2023/5/1649第49页，共65页。Example2.21(Pumpingdown)ep118cp76求证thatC={aibjck|0ijk}isnotcontext-free.Proof

Letpbethepumpinglength,ands=apbpcpC

P.L.:s=uvxyz,suchthatuvixyizCforeveryi0Twooptionsfor1|vxy|p:只有2种可能，分别讨论1)vxy=a*b*,thenthestringuv2xy2zhasnotenoughc’s,henceuv2xy2zC//在前面打圈，c的个数少2)vxy=b*c*,thenthestringuv0xy0z=uxz

hastoomanya’s,henceuv0xy0zCContradiction:Cisnotacontext-freelanguage.窍门：abc分段集中，且个数递增，用打圈破坏个数相等。第一步类似平面几何题的辅助线，神出鬼没，较难，2023/5/1650第50页，共65页。Ex2.22D={ww|w{0,1}*}(Ex.c3.22)ep119cp79求证它不是CFLCarefullytakethestringssD.

Letpbethepumpinglength,takes=0p1p0p1p.Threeoptionsfors=uvxyzwith1|vxy|p:

1)Ifapartofyistotheleftof|in0p1p|0p1p,

thensecondhalfofuv2xy2zstartswith“1”2)Samereasoningifapartofvistotheright

ofmiddleof0p1p|0p1p,henceuv2xy2zD3)Ifxisinthemiddleof0p1p|0p1p,thenuxz

equals0p1i0j1pD

(becauseiorj<p)Contradiction:Disnotcontext-free.2023/5/1651第51页，共65页。D={ww|w{0,1}*}(Ex.c2.22)ep119cp79求证它不是CFLCarefullytakethestringssD.

Letpbethepumpinglength,takes=0p1p0p1p.Threeoptionsfors=uvxyzwith1|vxy|p:

1)Ifapartofyistotheleftof|in0p1p|0p1p,

thensecondhalfofuv2xy2zstartswith“1”2)Samereasoningifapartofvistotheright

ofmiddleof0p1p|0p1p,henceuv2xy2zD3)Ifxisinthemiddleof0p1p|0p1p,thenuxz

equals0p1i0j1pD

(becauseiorj<p)Contradiction:Disnotcontext-free.2023/5/1652第52页，共65页。D={ww|w{0,1}*}(Ex.2.22)ep119cp79求证它不是CFLCarefullytakethestringssD.

Letpbethepumpinglength,takes=0p1p0p1p.Threeoptionsfors=uvxyzwith1|vxy|p:

1)Ifapartofyistotheleftof|in0p1p|0p1p,

thensecondhalfofuv2xy2zstartswith“1”2)Samereasoningifapartofvistotheright

ofmiddleof0p1p|0p1p,henceuv2xy2zD3)Ifxisinthemiddleof0p1p|0p1p,thenuxz

equals0p1i0j1pD

(becauseiorj<p)Contradiction:Disnotcontext-free.2023/5/1653第53页，共65页。PumpingProblems技巧UsingtheCFLpumpinglemmaismoredifficult

thanthepumpinglemmaforregularlanguages这一步类似平面几何题的辅助线，颇需巧思，较难。.

Youhavetochoosethestringscarefully,

anddividetheoptionsefficiently.

AdditionalCFLpropertieswouldbehelpful

(likewehadforregularlanguages).Whataboutclosureunderstandardoperations?2023/5/1654第54页，共65页。PumpingProblems技巧UsingtheCFLpumpinglemmaismoredifficult

thanthepumpinglemmaforregularlanguages这一步类似平面几何题的辅助线，颇需巧思，较难。.

Youhavetochoosethestringscarefully,

anddividetheoptionsefficiently.

AdditionalCFLpropertieswouldbehelpful

(likewehadforregularlanguages).Whataboutclosureunderstandardoperations?2023/5/1655第55页，共65页。UnionClosureProperties补充Lemma:LetA1andA2betwoCFlanguages,

thentheunionA1A2iscontextfreeaswell.CFL对并运算封闭（还是中文精炼）Proof:Assumethatthetwogrammarsare

G1=(V1,,R1,S1)andG2=(V2,,R2,S2).ConstructathirdgrammarG3=(V3,,R3,S3)by:V3=V1

V2

{S3}(newstartvariable)withR3=R1R2

{S3S1|S2}.ItfollowsthatL(G3)=L(G1)L(G2).下页有直观解释2023/5/1656第56页，共65页。UnionClosureProperties补充Lemma:LetA1andA2betwoCFlanguages,

thentheunionA1A2iscontextfreeaswell.CFL对并运算封闭（还是中文精炼）Proof:Assumethatthetwogrammarsare

G1=(V1,,R1,S1)andG2=(V2,,R2,S2).ConstructathirdgrammarG3=(V3,,R3,S3)by:

V3=V1

V2

{S3}(newstartvariable)withR3=R1R2

{S3S1|S2}.ItfollowsthatL(G3)=L(G1)L(G2).下页有直观解释2023/5/1657第57页，共65页。UnionClosureProperties补充Lemma:LetA1andA2betwoCFlanguages,

thentheunionA1A2iscontextfree