計算理論02-正則語言

2023/1/311第二講課程

Chapter1:RL=RegularLanguages,nonregularlanguagesRLpumpinglemmaChapter2:Context-FreeLanguages(CFLs)2023/1/312RegularExpressions

(Def.1.26中文：定義1.26)

ep64cp39遞歸法下定義，適合本身是遞歸結(jié)構(gòu)的對象例

N!或記為F(N)定義為F(0)=1;遞歸基礎(chǔ)（程序終止條件）F(N)=N*F(N-1)當N>=1//遞歸(減1）結(jié)構(gòu)IntFactor(intn){if(n<0)printf(“error”);ifn==0return1;//無此語句，會導(dǎo)致errorelsereturnn*Factor(n-1);//通常用棧結(jié)構(gòu)實現(xiàn)}如第1,2句均無，則死循環(huán)，稱為圖靈機不停機，2023/1/313RegularExpressions正則表達式

(Def.1.26中文：定義1.26)

ep64cp38遞歸法下定義，適合本身是遞歸結(jié)構(gòu)的對象，構(gòu)造性的Givenanalphabet,RisaregularexpressionifR=a,withaR=遞歸基礎(chǔ)R=R=(R1R2),withR1andR2regularexpressionsR=(R1R2),withR1andR2regularexpressionsR=(R1*),withR1aregularexpression遞歸結(jié)構(gòu)，增加一個運算符號的構(gòu)造方法2023/1/314Thm1.28:RL~REep66cp40（讀一下）Thm1.28

LisRLthereexistsREEsuchthatL=E

通常L={..|….}E形如(a+b)C+(d.g)*

(無窮)集合表達式有限字母有限運算構(gòu)造，可計算Weneedtoprovebothways:左邊右邊Ifalanguageisdescribedbyaregularexpression,

thenitisregular(Lemma1.29)上次實際上已證左邊右邊(Lastweekwesawhowwecanconvertaregular

expressionRintoanNFAMsuchthatL(R)=L(M))上次已完成FA的確定化Todaywedothesecondpart:左邊右邊,給機造表達式Ifalanguageisregular,thenitcanbedescribedby

aregularexpression(Lemma1.32)2023/1/315Thm1.28:RL~RE給機造表達式

ep66cp40（讀一下）Todaywedothesecondpart:左邊右邊，即：Ifalanguageisregular,thenitcanbedescribedby

aregularexpression(Lemma1.32)分兩部1RL有DFAM識別（定義），把DFA轉(zhuǎn)化稱廣義的GNFA2把廣義的GNFA轉(zhuǎn)化成正則表達式RE下頁先引入廣義的GNFA普通的NFA中一個邊相當于一個語句廣義的GNFA

自動機的邊可以是正則表達式（自動機），相當相當于程序可以調(diào)用（子）程序2023/1/316GeneralizedNFA給機造表達式ep70-73,cp41-42Generalizednondeterministicfiniteautomaton

M=(Q,,,qstart,qaccept)withQfinitesetofstatestheinputalphabetqstartthestartstateqaccepttheacceptstate:(Q\{qaccept})(Q\{qstart})Rthetransitionfunction(R

isthesetofregularexpressionsover)

惟一區(qū)別自動機的邊是

RE(子程序，子自動機）狀態(tài)不包括終點下一狀態(tài)，不包括起點2023/1/317ExampleGNFA

與ep70圖稍有不同qSqA01*00*110110子自動機2023/1/318CharacteristicsofGNFA’s:(Q\{qaccept})(Q\{qstart})RTheinteriorQ\{qaccept,qstart}isfullyconnectedbyFromqstartonly‘outgoingtransitions’Toqacceptonly‘ingoingtransitions’Impossibleqiqjtransitionsare“(qi,qj)=”qSqARRObservation:ThisGNFA:

recognizesthe

languageL(R)除開起止點，稱為內(nèi)部狀態(tài)2023/1/319ProofIdeaofLemmac2.32給機造表達式

,ep69,cp41Proofidea(givenaDFAM):

ConstructanequivalentGNFAM’withk2statesReduceone-by-onetheinternalstatesuntilk=2逐個等價地減少狀態(tài)，把內(nèi)部的表達式變大ThisGNFAwillbeoftheformThisregularexpressionR

willbesuchthatL(R)=L(M)qSqAR2023/1/3110DFAMEquivalentGNFAM’

給機造表達式ep73cp42LetMhavekstatesQ={q1,…,qk}-Addtwostatesqacceptandqstart加首尾補空邊qSq1-Connectqstarttoearlierq1:qiqj-CompletemissingtransitionsbyqAqj-Connectoldacceptingstatestoqaccept-Joinmultipletransitions:合并標號qi0qj1becomesqi01qj2023/1/3111qiR4(R1R2*R3)qjqiR2qjR4qripR1R3=RemoveInternalstateofGNFA

給機造表達式ep73IftheGNFAMhasmorethan2states,‘rip’

internalqriptogetequivalentGNFAM’by:-Removingstateqrip:Q’=Q\{qrip}逐步減少內(nèi)態(tài)Changingthetransitionfunctionby

’(qi,qj)=(qi,qj)((qi,qrip)((qrip,qrip))*(qrip,qj))

foreveryqiQ’\{qaccept}andqjQ’\{qstart}法則：用力拉首尾，拓撲變形。以星換圈，以并換多路2023/1/3112ProofLemma1.32給機造表達式ep69LetMbeDFAwithkstates此頁可略CreateequivalentGNFAM’withk+2statesReduceinkstepsM’toM’’with2statesTheresultingGNFAdescribesasingleregular

expressionsRTheregularlanguageL(M)equalsthelanguage

L(R)oftheregularexpressionR2023/1/3113RegularLanguages=RegularExpressions

ep74cp45LetRbearegularexpression,thenthereexists

anNFAMsuchthatL(R)=L(M)正則有DFA

ThelanguageL(M)ofaDFAMisequivalentto

alanguageL(M’)ofaGNFA=M’,whichcan

beconvertedtoatwo-stateM’’DFA等價于GNFAThetransitionqstart

RqacceptofM’’

obeysL(R)=L(M’’)GNFA等價于正則語言Hence:RENFA=DFAGNFARE它們的表達能力等價2023/1/3114NonregularLanguages§1.4ep77學，然后知”不足”，正則語言表達能力有限絕大多數(shù)語言是NRLWhichlanguagescannotberecognizedbyfinite

automata?Example:L={0n1n|nN}NRL‘Playingaround’withFAconvincesyouthatthe

‘finiteness’ofFAisproblematicfor“allnN”Theproblemoccursbetweenthe0nandthe1n要證明它不是NRL需要泵定理引入泵定理Informal:thememoryofaFAislimitedbythe

thenumberofstates|Q|,原因，F(xiàn)A的軟硬件太少2023/1/3115將討論Pumping定理q1qkqj思想：言多必復(fù):設(shè)一個羅嗦老太婆，有n個論點，當說話多于n句時，至少有一個地方在打圈,(發(fā)言激動時尤其如此），以后遇此，可笑談：泵定理其作用了。正則語言是靠打圈，才描述無限集合的2023/1/3116RepeatingDFAPathsep79cp48q1qkqjConsideranacceptingDFAMwithsize|Q|機器狀態(tài)數(shù)Onastringoflengthp,p+1states（識別某詞的狀態(tài)路徑長度）

getvisitedForp|Q|,theremustbeqjsuchthatthe

computationalpathlookslike:q1,…,qj,…,qj,…,qk打圈2023/1/3117RepeatingDFAPathsep79cp48q1qkqjTheactionoftheDFAinqjisalwaysthesame.Ifwerepeat(orignore)theqj,…,qjpart,thenew

pathwillagainbeanacceptingpath不確定自動機，多路并行打圈，語無倫次時是不確定的2023/1/3118PumpingLemma(Thm1.37)ep78ForeveryregularlanguageL,thereisa

pumpinglengthp,suchthatforanystring

sLand|s|p,wecanwrites=xyzwith

1)xyizLforeveryi{0,1,2,…}中間羅嗦2)|y|>0

3)|xy|p開講后不久，就打圈Notethat1)impliesthatxzL（重要）

2)saysthatycannotbetheemptystring

Condition3)isnotalwaysused

經(jīng)得起泵測試（容忍羅嗦）是RL的必要條件（不充分）長度超過自動機狀態(tài)數(shù)的單詞必有一處y打圈（真圈）2023/1/3119FormalProofofPumpingLemmaep78證明細節(jié)，自學LetM=(Q,,,q1,F)withQ={q1,…,qp}Lets=s1…snL(M)with|s|=np泵長為狀態(tài)數(shù)ComputationalpathofMonsisthe

sequencer1,…,rn+1Qn+1with

r1=q1,rn+1Fandrt+1=(rt,st)for1tnBecausen+1p+1,therearetwostates

suchthatrj=rk(withj<kandkp+1)Letx=s1…sj–1,y=sj…sk–1,andz=sk…sn+1xtakesMfromq1=r1torj,ytakesMfromrjtorj,

andztakesMfromrjtorn+1FAsaresult:xyiztakesMfromq1torn+1F(i0)鴿巢原理至少一處打圈2023/1/3120FormalProofofPumpingLemmaep78

證明細節(jié)，自學LetM=(Q,,,q1,F)withQ={q1,…,qp}Lets=s1…snL(M)with|s|=npComputationalpathofMonsisthe

sequencer1,…,rn+1Qn+1with

r1=q1,rn+1Fandrt+1=(rt,st)for1tnBecausen+1p+1,therearetwotermssuchthatrj=rk(withj<kandkp+1),Letx=s1…sj–1,y=sj…sk–1,andz=sk…sn+1xtakesMfromq1=r1torj,ytakesMfromrjtorj,

andztakesMfromrjtorn+1FAsaresult:xyiztakesMfromq1torn+1F(i0)|y|1and|xy|pxyizL(M)foreveryi{0,1,2,…}2023/1/3121Pumping0n1n(Ex.c2.38)證明它不是RLep80,cp49Countproof（reductiontoabsurdity）反證法AssumethatB={0n1n|n0}isregularLetpbethepumpinglength,ands=0p1pBP.L.:s=xyz=0p1p,withxyizBforalli0Threeoptionsfory:用i=2就推出矛盾了 1)y=0k,hencexyyz=0p+k1pB 2)y=1k,hencexyyz=0p1k+pB 3)y=0k1l,hencexyyz=0p1l0k1pBConclusion:Thepumpingresultdoesnothold,

thelanguageBisnotregular.小結(jié)泵定理技巧，一個元素在RL中打圈的無窮個也在RL中，經(jīng)不起泵測試就不是RL.矛盾2023/1/3122證明F={ww|w{0,1}*}不是RL

Ex.c2.40，ep81，cp50反證法Letpbethepumpinglength,andtake足夠長的words=0p10p1,W=0p1

Lets=xyz=0p10p1,withcondition3)|xy|p開講后不久就打圈Onlyoneoption:x=0p-k

,y=0k,z=10p-k1,(保證xzinL)withxyyz=0p+k10p-k1

FWithout3)thiswouldhavebeenapain.2023/1/3123Interse