形式語言與自動機理論

FormalLanguagesandAutomataTheory蔣宗禮形式語言與自動機理論

FormalLanguagesan1課程目的和基本要求課程性質技術基礎

基礎知識要求

數學分析（或者高等數學），離散數學

主要特點

抽象和形式化

理論證明和構造性

基本模型的建立與性質

課程目的和基本要求課程性質2課程目的和基本要求本專業人員4種基本的專業能力計算思維能力算法的設計與分析能力程序設計和實現能力計算機軟硬件系統的認知、分析、設計與應用能力計算思維能力邏輯思維能力和抽象思維能力構造模型對問題進行形式化描述理解和處理形式模型課程目的和基本要求本專業人員4種基本的專業能力3課程目的和基本要求

知識掌握正則語言、下文無關語言的文法、識別模型及其基本性質、圖靈機的基本知識。能力培養學生的形式化描述和抽象思維能力。使學生了解和初步掌握“問題、形式化描述、自動化（計算機化）”這一最典型的計算機問題求解思路。課程目的和基本要求知識4主要內容

語言的文法描述。RLRG、FA、RE、RL的性質。CFLCFG(CNF、GNF)、PDA、CFL的性質。

TM基本TM、構造技術、TM的修改。CSLCSG、LBA。主要內容語言的文法描述。5教材及主要參考書目蔣宗禮，姜守旭.形式語言與自動機理論.北京：清華大學出版社，2003年

JohnEHopcroft,RajeevMotwani,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation(2ndEdition).Addison-WesleyPublishingCompany,2001JohnEHopcroft,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation.Addison-WesleyPublishingCompany,1979教材及主要參考書目蔣宗禮，姜守旭.形式語言與自動機理論.6第8章CFL的性質本章討論CFL的性質主要內容CFL的泵引理及其應用、Ogden引理。CFL的封閉性封閉運算：并、乘、閉包、代換、同態映射、逆同態映射不封閉運算：交、補第8章CFL的性質本章討論CFL的性質7第8章上下文無關語言的性質CFL的判定算法。判定CFG產生的語言是否為空、有窮、無窮。一個給定的符號串是否為該文法產生的語言的一個句子等問題。

重點CFL的封閉性、CFL的泵引理。

難點CFL的泵引理的應用、CFL的同態原象是CFL。

第8章上下文無關語言的性質CFL的判定算法。88.1上下文無關語言的泵引理啟發RGG=(V，T，P，S)，使得L(G)=L，當x足夠長時，如|x|≥|V|+1時，存在u、v、w∈T*，|v|≥1，使得x=uvw，當G為右線性文法時，必定存在語法變量A，使得如下派生成立：S*uA*uvA*……*uviA*uviw

V是可以被重復任意多次的字串！CFL也有類似性質？8.1上下文無關語言的泵引理啟發98.1上下文無關語言的泵引理CFL的自嵌套特性：如果L是一個CFL，CFGG=(V，T，P，S)是產生L的文法。當L是一個無窮語言時，必存在w∈L，A∈V，α，β∈(V∪T)*，且α和β中至少有一個不為ε，使得如下派生成立 S*γAδ+γαAβδ+z文法G中存在有如下形式的派生 A+αAβ

8.1上下文無關語言的泵引理CFL的自嵌套特性：如果L是一10

8.1上下文無關語言的泵引理這種類型的派生預示著S*γAδ+γαAβδ+z并且S*γAδ+γαnAβnδ+z′設α*v，β*x，γ*u，A*w，δ*y可以得到如下派生8.1上下文無關語言的泵引理這種類型的派生預示著118.1上下文無關語言的泵引理S*γAδ*uαAβδ*uαAβy…*uαnAβny*uvnAxny*uvnwxny8.1上下文無關語言的泵引理S*γAδ128.1上下文無關語言的泵引理

引理8-1（CFL的泵引理）對于任意的CFLL，存在僅僅依賴于L的正整數N，對于任意的z∈L，當|z|≥N時，存在u，v，w，x，y，使得z=uvwxy，同時滿足：(1)|vwx|≤N；(2)|vx|≥1；(3)對于任意的非負整數i，uviwxiy∈L。

8.1上下文無關語言的泵引理138.1上下文無關語言的泵引理8.1上下文無關語言的泵引理148.1上下文無關語言的泵引理證明要點：（1）用CNF作為CFL的描述工具。（2）對于任意的z∈L，當k是z的語法樹的最大路長時，必有|z|≤2k-1成立。（3）僅當z的語法樹呈圖8-1所示的滿二元樹時，才有|z|=2k-1，其他時候均有|z|<2k-1。（4）取N=2|V|=2|V|+1-1，z∈L，|z|≥N。8.1上下文無關語言的泵引理證明要點：158.1上下文無關語言的泵引理8.1上下文無關語言的泵引理168.1上下文無關語言的泵引理（5）取z的語法樹中的最長的一條路p，p中的非葉子結點中必定有不同的結點標有相同的語法變量。（6）p中最接近葉子且都標有相同的語法變量A的兩個結點為v1、v2，如圖8-2所示。8.1上下文無關語言的泵引理（5）取z的語法樹中的最長的178.1上下文無關語言的泵引理結點v1左邊的所有葉子結點的標記從左到右構成的字符串為u；結點v1的為根的子樹中，v2左邊的所有葉子結點的標記從左到右構成的字符串為v；結點v2為根的子樹的結果為w；結點v1為根的子樹中v2右邊的所有葉子結點的標記從左到右構成的字符串為x；結點v1右邊的所有葉子結點的標記從左到右構成的字符串為y。

8.1上下文無關語言的泵引理結點v1左邊的所有葉子結點的標188.1上下文無關語言的泵引理z=uvwxy注意到v1-子樹的最大路長小于等于|V|+1，所以，v1的結果vwx滿足：|vwx|≤2(|V|+1)-1=2|V|=Nv1的后代v2標記為變量A，所以，|vx|≥1。此時有S*uAy+uvAxy+uvwxy顯然，對于i=0，1，2，3，…A*viAxi

+viwxi

8.1上下文無關語言的泵引理z=uvwxy198.1上下文無關語言的泵引理總結上述推導（7）S*uAy+uvAxy+uvwxy=z，|vwx|≤2(|V|+1)-1=2|V|=N，|vx|≥1。（8）對于任意非負整數i，S*uAy+uviAxiy+uviwxiy。8.1上下文無關語言的泵引理總結上述推導208.1上下文無關語言的泵引理例8-1證明L={anbncn|n≥1}不是CFL。

證明：取z=aNbNcN∈L

⑴v=ah，x=bf，h+f≥1。uviwxiy=aN+(i-1)hbN+(i-1)fcN，當i≠1時，N+(i-1)h≠N和N+(i-1)f≠N中至少有一個成立。uviwxiy=aN+(i-1)hbN+(i-1)fcNL。8.1上下文無關語言的泵引理例8-1證明L={anbn218.1上下文無關語言的泵引理⑵v=bh，x=cf，h+f≥1。uviwxiy=aNbN+(i-1)hcN+(i-1)f當i≠1時，N+(i-1)h≠N和N+(i-1)f≠N中至少有一個成立。uviwxiy=aNhbN+(i-1)cN+(i-1)f

L。這些都與泵引理矛盾，所以，L不是CFL。

8.1上下文無關語言的泵引理⑵v=bh，x=cf，h+f228.1上下文無關語言的泵引理例8-2證明L={anbmcndm|n，m≥1}不是CFL。

證明：取z=aNbNcNdN

v=ah、x=bf；v=bh、x=cf；v=ch、x=df，h+f≥1等4種情況。

8.1上下文無關語言的泵引理例8-2證明L={anbmc238.1上下文無關語言的泵引理設v=ah、x=bf，并且h+f≥1uviwxiy=aN+(i-1)hbN+(i-1)fcNdN當i≠1時，N+(i-1)h≠N和N+(i-1)f≠N至少有一個成立。uviwxiy=aN+(i-1)hbN+(i-1)fcNdNL

8.1上下文無關語言的泵引理設v=ah、x=bf，并且h+248.1上下文無關語言的泵引理同理可以證明，當v=bh、x=cf或者v=ch、x=df，h+f≥1時， uviwxiy=aN+(i-1)hbN+(i-1)fcNdNL 對i≠1成立。

由泵引理，L不是CFL。

8.1上下文無關語言的泵引理同理可以證明，當v=bh、x=258.1上下文無關語言的泵引理L={anbmck|n≠m，m≠k，k≠n}是CFL么？取z=aNbN+ncN+m其中，n≠m，n≠0，m≠0。只能讓v或者x由若干個a組成，才有可能隨著i的變化，使得uviwxiy中a的個數與b的個數或者c的個數相同。

當v=ak，x=bh（N≥k≥1），顯然，只要令k=h，就能保證對于任意的i，uviwxiy中字符a的個數永遠不能等于字符b的個數。希望uviwxiy中字符a的個數等于字符c的個數。8.1上下文無關語言的泵引理L={anbmck|n≠m，m268.1上下文無關語言的泵引理想辦法保證在N≥k≥1的條件下，總能找到一個i，使得uviwxiy中字符a的個數能夠等于c的個數。

在uviwxiy中，字符a的個數為N+(i-1)k，而c的個數為N+m，即：N+(i-1)k=N+m。從而要求，無論k取N到1的任何一個值，i=m/k+1必須是一個整數。

8.1上下文無關語言的泵引理想辦法保證在N≥k≥1的條件下278.1上下文無關語言的泵引理取z=aNbN+N!cN+2N!

v=ak，x=bh，N≥k≥1

當i=2N!/k+1時，有uviwxiy=aN+(i-1)kbN+N!+(i-1)hcN+2N!=aN+(2N!/k+1-1)kbN+N!+(2N!/k+1-1)hcN+2N!=aN+(2N!/k)kbN+N!+(2N!/k)hcN+2N!=aN+2N!bN+N!+(2N!/k)hcN+2N!uviwxiy=aN+2N!bN+N!+(2N!/k)hcN+2N!

L。

8.1上下文無關語言的泵引理取z=aNbN+N!cN+2N288.1上下文無關語言的泵引理問題：當取v=bk，x=ch，N≥k≥1，時，我們就無法在找到矛盾了。

我們必須把目標鎖定在a上！因為這能保證找出“矛盾”！所以我們實在是對a太“感興趣”了！稱這些令我們感興趣的字符為特異點(distinguishedposition)。8.1上下文無關語言的泵引理問題：當取v=bk，x=ch，298.1上下文無關語言的泵引理？是否可以要求v和x中必須含有a。這樣必須修改原有的泵引理！定義z的語法樹滿足下列條件的非葉子結點為分支點(branchpoint)：該結點有兩個兒子，并且它的這兩個兒子均有特異點后代。

8.1上下文無關語言的泵引理？是否可以要求v和x中必須含有308.1上下文無關語言的泵引理引理8-2（Ogden引理）對于任意的CFLL，存在僅僅依賴于L的正整數N，對于任意的z∈L，當z中至少含有N個特異點時，存在u，v，w，x，y，使得z=uvwxy，同時滿足:

(1)|vwx|中特異點的個數≤N；(2)|vx|中特異點的個數≥1；(3)對于任意的非負整數i，uviwxiy∈L。8.1上下文無關語言的泵引理318.1上下文無關語言的泵引理證明要點：（1）與CFL的泵引理的證明類似。（2）用CNF作為CFL的描述工具。（3）取N=2|V|+1。（4）構造從樹根到葉子的含有最多分支點的路徑p。參考圖8-2。8.1上下文無關語言的泵引理證明要點：328.1上下文無關語言的泵引理圖8-2z的派生樹8.1上下文無關語言的泵引理圖8-2z的派生樹338.1上下文無關語言的泵引理其中：結點v1左邊的所有葉子結點的標記從左到右構成的字符串為u；結點v1的為根的子樹中v2左邊的所有葉子結點的標記從左到右構成的字符串為v；結點v2為根的子樹的結果為w；結點v1的為根的子樹中v2右邊的所有葉子結點的標記從左到右構成的字符串為x；結點v1右邊的所有葉子結點的標記從左到右構成的字符串為y；8.1上下文無關語言的泵引理其中：348.1上下文無關語言的泵引理（5）

p中至少有|V|+1個分支點，在這些分支結點中，至少有兩個不同的結點標記有相同的變量A。（6）仍然參照圖8-2，p中最接近葉子的且都標有相同的語法變量A的兩個分支結點為v1、v2。（7）S*uAy+uvAxy+uvwxy=z。vwx中最多有N個特異點，vx至少有1個特異點。（8）對于任意的非負整數i，S*uAy+uviAxiy+uviwxiy。8.1上下文無關語言的泵引理（5）

p中至少有|V|+1358.1上下文無關語言的泵引理例8-3證明L={anbmchdj|n=0或者m=h=j}不是CFL。

取z=abNcNdN

⑴v=a，x=bk，k≠0此時uv2wx2y=aabN+kcNdNL；⑵v=bk，x=cg，k≠0，g≠0此時uv2wx2y=abN+kcN+gdNL；⑶v=bk，x=dg，k≠0，g≠0此時uv2wx2y=aabN+kcNdN+gL；與Ogden引理矛盾，所以，L不是CFL。8.1上下文無關語言的泵引理例8-3證明L={anbmc368.2CFL的封閉性定理8-1CFL在并、乘積、閉包運算下是封閉的。

證明要點：令CFGG1=(V1，T1，P1，S1)，L(G1)=L1，G2=(V2，T2，P2，S2)，L(G2)=L2，V1∩V2=Φ，且S3，S4，S5V1∪V2。

8.2CFL的封閉性定理8-1CFL在并、乘積、378.2CFL的封閉性G3=(V1∪V2∪{S3},T1∪T2,P1∪P2∪{S3

S1|S2},S3)G4=(V1∪V2∪{S4},T1∪T2,P1∪P2∪{S4

S1S2},S4)G5=(V1∪{S5}，T1，P1∪{S5

S1S5|ε}，S5)顯然，G3、G4、G5都是CFG，并且 L(G3)=L1∪L2L(G4)=L1L2L(G5)=L1*8.2CFL的封閉性G3=(V1∪V2∪{S3},T1∪388.2CFL的封閉性定理8-2CFL在交運算下不封閉的。

證明要點：

設L1={0n1n2m|n,m≥1}，L2={0n1m2m|n,m≥1}。 G1：S1AB A0A1|01 B2B|2G2：SAB A0A|0 B1B2|128.2CFL的封閉性定理8-2CFL在交運算下不398.2CFL的封閉性顯然，L(G1)=L1、L(G2)=L2。L=L1∩L2={0n1n2n|n≥1}不是CFL。所以，CFL在交運算下是不封閉的。

8.2CFL的封閉性顯然，L(G1)=L1、L(G2)=408.2CFL的封閉性推論8-1CFL在補運算下是不封閉的。

證明要點：由于CFL對并運算的封閉性、對交運算的不封閉性和下列式子，可以得出CFL對補運算是不封閉的結論。

8.2CFL的封閉性推論8-1CFL在補運算下是不封418.2CFL的封閉性定理8-3CFL與RL的交是CFL。證明：（1）構造設PDAM1=(Q1，∑，Γ，δ1，q01，Z0，F1) L1=L(M1)DFAM2=(Q2，∑，δ2，q02，F2) L2=L(M2)8.2CFL的封閉性定理8-3CFL與RL的交是CF428.2CFL的封閉性取PDAM=(Q1×Q2，∑，Γ，δ，[q01，q02]，Z0，F1×F2)對([q，p]，a，Z)∈(Q1×Q2)×(∑∪{ε})×Γ

δ([q，p]，a，Z)={([q′，p′]，γ)|(q′,γ)∈δ1(q，a，Z)且p′=δ(p，a)}可以用下圖標是構造的基本思想。

8.2CFL的封閉性取PDAM=(Q1×Q2，∑，Γ，438.2CFL的封閉性8.2CFL的封閉性448.2CFL的封閉性①M使用的棧就是M1的棧。②M的狀態包括兩個分量：一個為M1的狀態，用來使M的動作能準確地模擬M1的動作；另一個為M2的狀態，用來使M的動作能準確地模擬M1的動作。③當M1執行ε-移動時，M2不執行動作。8.2CFL的封閉性①M使用的棧就是M1的棧。458.2CFL的封閉性(2)證明構造的正確性。施歸納于n證明： ([q01，q02]，w，Z0)├Mn([q，p]，ε，γ)(q01，w，Z0)├M1n(q，ε，γ)&δ(q02，w)=p再注意到[q，p]∈F1×F2q∈F1&p∈F2這就是說，對于x∈∑*， x∈L(M)x∈L(M1)&x∈L(M2)所以， L(M)=L(M1)∩L(M2)

8.2CFL的封閉性(2)證明構造的正確性。468.2CFL的封閉性根據本定理證明中給出的方法，可以用N個正則語言L1、L2、…、LN的識別器(DFA)的有窮狀態控制器構成這N個正則語言的交的識別器(DFA)： M∩=(Q1×Q2×…×QN，∑，δ，[q10，q20，…，qN0]，F1×F2×…×FN)

8.2CFL的封閉性根據本定理證明中給出的方法，可以用N478.2CFL的封閉性定理8-4

CFL在代換下是封閉的。①CFGG=(V，T，P，S)，使得L=L(G)。對于a∈T，f(a)是∑上的CFL，且CFGGa=(Va，∑，Pa，Sa)，使得f(a)=L(Ga)。②f(a)的所有句子都是由Sa派生出來的，所以，構造的基本思想是用Sa替換產生L的CFG的產生式中出現的終極符號a。8.2CFL的封閉性定理8-4CFL在代換下是封閉的488.2CFL的封閉性③產生f(L)的文法8.2CFL的封閉性③產生f(L)的文法498.2CFL的封閉性④證明L(G′)=f(L)設x∈L(G′)，從而S*G′SaSb…Sc+G′xaSb…Sc+G′xaxb…Sc…+G′xaxb…xc=xSa，Sb，…，Sc∈{Sd|d∈T}。且Sa*G′xaSb*G′xb…Sc

*G′xc8.2CFL的封閉性④證明L(G′)=f(L)Sa，S508.2CFL的封閉性由G′的定義知，S*G′SaSb…Sc

S*Gab…c并且，對于d∈T， Sd*G′xd

Sd*Gdxd

所以，ab…c∈L，xa∈L(Ga)，xb∈L(Gb)，…，xc∈L(Gc)故：x=xaxb…xc=f(a)f(b)…f(c)=f(ab…c)即：x∈f(L)。從而L(G′)f(L)用類似的方法，不難證明f(L)L(G′)。綜上所述，定理得證。8.2CFL的封閉性由G′的定義知，518.2CFL的封閉性推論8-2CFL的同態像是CFL。

注意到對任意的CFGG=(V，T，P，S)，L=L(G)。對于a∈T，|f(a)|=1，所以它是∑上的CFL，根據這個定理，得到此推論。

8.2CFL的封閉性推論8-2CFL的同態像是CFL。528.2CFL的封閉性定理8-5CFLL的同態原像是CFL。

基本思路：①描述工具PDA。②

PDAM2=(Q2，∑2，Γ，δ2，q0，Z0，F)接受L③

設T={a1，a2，…，an}根據f(a1)=x1，f(a2)=x2，…，f(an)=xn，M1有窮控制器中的緩沖區存放f(a1)，f(a2)，…，f(an)的任一后綴。8.2CFL的封閉性定理8-5CFLL的同態原像是538.2CFL的封閉性④

對于任意的x∈∑1*，設x=b1b2…bn，M1是否接受x，完全依據于M2是否接受f(b1)f(b2)…f(bn)。⑤M1的形式定義為M1=(Q1，∑1，Γ，δ1，[q0，ε]，Z0，F×{ε})Q1={[q，x]|q∈Q2，存在a∈∑1，x是f(a)的后綴}當M1掃描到a∈∑1時，將f(a)存入有窮控制器，([q，f(a)]，A)∈δ1([q，ε]，a，A)8.2CFL的封閉性④

對于任意的x∈∑1*，設x=b1b548.2CFL的封閉性然后，M1模擬M2處理存在緩沖區中的f(a)。M1用ε-移動模擬M2的非ε-移動：(p，γ)∈δ2(q，a，A)， ([p，x]，γ)∈δ1([q，ax]，ε，A)M1用ε-移動模擬M2的ε-移動(p，γ)∈δ2(q，ε，A)，

([p，x]，γ)∈δ1([q，x]，ε，A)8.2CFL的封閉性然后，M1模擬M2處理存在緩沖區中的f55圖8-4M的構造示意圖圖8-4M的構造示意圖568.2CFL的封閉性構造的正確性證明。

證明x=a1a2…an∈L(M1)的充分必要條件是f(a1)f(a2)…f(an)∈L(M2)，這里的關鍵是對狀態“接續”的理解。也就是

8.2CFL的封閉性構造的正確性證明。578.2CFL的封閉性成立的充分必要條件為：([qi，ε]，ai…an，γi)├M1

([qi，f(ai)]，ai+1…an，γi)([qi，f(ai)]，ai+1…an，γi)├M1*([qi+1，ε]，ai…an，γi+1)(q0，f(a1)f(a2)…f(an)，Z0)├M2*(q1，f(a2)…f(an)

，γ1)(qi，f(ai)…f(an)

，γi)├M2*(qi+1，f(ai+1)…f(an)，γi+1)8.2CFL的封閉性成立的充分必要條件為：([qi，ε]，588.3CFL的判定算法不存在判斷算法的問題：①

CFGG，是不是二義性的？②

CFLL的補是否確實不是CFL？③

任意兩個給定CFG是等價的么？存在判斷算法的問題：④L是非空語言么？⑤L是有窮的么？⑥一個給定的字符串x是L的句子么？

8.3CFL的判定算法不存在判斷算法的問題：598.3.1L空否的判定基本思想：設L為一個CFL，則存在CFGG，使得L(G)=L。由算法6-1，我們可以求出等價的CFGG′，G′中不含派生不出終極符號行的變量。顯然，如果NEWV中包含G的開始符號，則L就是非空的。否則，L就是空的。因此，通過改造算法6-1，我們可得到判定L是否為空的算法8-1。

8.3.1L空否的判定基本思想：608.3.1L空否的判定算法8-1判定CFLL是否為空。輸入：CFGG=(V，T，P，S)。輸出：G是否為空的判定；CFGG′=(V′，T，P′，S)，V′中不含派生不出終極符號行的變量，并且有L(G′)=L(G)。主要步驟：(1)

OLDV=Φ；(2)NEWV={A|Aw∈P且w∈T*}

8.3.1L空否的判定算法8-1判定CFLL是否618.3.1L空否的判定(3)

whileOLDV≠NEWVdo begin(4)

OLDV=NEWV；(5)

NEWV=OLDV∪{Aα∈P且 α∈(T∪OLDV)*}； end(6)

V′=NEWV；(7)

P′={Aα|Aα∈P且A∈V′且 α∈(T∪V′)*}；(8)

ifS∈NEWVthenL(G)非空elseL(G)為空8.3.1L空否的判定(3)

whileOLD628.3.2L是否有窮的判定可派生性圖表示(DerivabilityGraphofG——DG)

設CFGG=(V，T，P，S)，G的可派生性圖表示是滿足下列條件的有向圖：(1)

對于X∈V∪T，圖中有且僅有一個標記為X的頂點；(2)

如果AX1X2…Xn∈P，則圖中存在從標記為A的頂點分別到標記為X1、X2、…、Xn的弧；(3) 圖中只有滿足條件1和2的頂點和弧。

8.3.2L是否有窮的判定可派生性圖表示(Deriva638.3.2L是否有窮的判定G的可派生性圖表示中，任意兩個頂點之間最多有一條相同方向的弧。

G的可派生性圖表示表達了文法G中的語法變量之間的派生關系。

派生A+αAβ存在的充分必要條件是G的可派生性圖表示中存在一條從標記為A的頂點到標記為A的頂點的長度非0的有向回路。

8.3.2L是否有窮的判定G的可派生性圖表示中，任意兩648.3.2L是否有窮的判定定理8-6設CFGG=(V，T，P，S)不含無用符號，L(G)為無窮語言的充分必要條件是G的可派生性圖表示中存在一條有向回路。

證明要點：對應某一條有向回路，尋找一條從S出發，到達此回路的路，可以構造出下列形式的派生 S+γAρ+γαAβρ從而對任意的非負整數i， S+γAρ+γαiAβiρ

8.3.2L是否有窮的判定定理8-6設CFGG658.3.2L是否有窮的判定DG中標記為終極符號的結點是無用的簡化的可派生性圖表示(simplifiedderivabilitygraphofG，SDG)設CFGG=(V，T，P，S)，G的簡化的可派生性圖表示是從G的可派生性圖表示中刪除所有標記為終極符號的頂點后得到的圖。8.3.2L是否有窮的判定DG中標記為終極符號的結點是668.3.2L是否有窮的判定定理8-7設CFGG=(V，T，P，S)不含無用符號，L(G)為無窮語言的充分必要條件是G的簡化的可派生性圖表示中存在一條有向回路。證明：與定理8-6的證明類似。8.3.2L是否有窮的判定定理8-7設CFGG678.3.2L是否有窮的判定算法8-2判定CFLL是否為無窮語言。輸入：CFGG=(V，T，P，S)。輸出：G是否為無窮的判定；CFGG′=(V′，T，P′，S)，V′中不含派生不出終極符號行的變量，并且有L(G′)=L(G)。8.3.2L是否有窮的判定算法8-2判定CFLL688.3.2L是否有窮的判定(1)

調用算法6-1、6-2；(2)ifSV′thenL(G)為有窮的語言 else begin(3)構造G′的簡化的可派生性圖表示SDG；(4)ifSDG中含有回路thenL(G′)為無窮語言(5)elseL(G′)為有窮有語言。

end8.3.2L是否有窮的判定(1)

調用算法6-1、698.3.3x是否為L的句子的判定

判斷x是否為給定文法生成的句子的根本方法是看G能否派生出x。一種最簡單的算法是用窮舉法，這種方法又稱為“試錯法”,是“帶回溯”的，所以效率不高。其時間復雜度為串長的指數函數。

典型的自頂向下的分析方法：遞歸子程序法、LL(1)分析法、狀態矩