蔣宗禮送形式語言與自動機理論課件

形式語言與自動機理論

FormalLanguagesandAutomataTheory

蔣宗禮7/22/20231課程目的和基本要求課程性質(zhì)技術(shù)基礎(chǔ)

基礎(chǔ)知識要求

數(shù)學(xué)分析（或者高等數(shù)學(xué)），離散數(shù)學(xué)

主要特點

抽象和形式化

理論證明和構(gòu)造性

基本模型的建立與性質(zhì)

7/22/20232課程目的和基本要求本專業(yè)人員4種基本的專業(yè)能力計算思維能力算法的設(shè)計與分析能力程序設(shè)計和實現(xiàn)能力計算機軟硬件系統(tǒng)的認知、分析、設(shè)計與應(yīng)用能力計算思維能力邏輯思維能力和抽象思維能力構(gòu)造模型對問題進行形式化描述理解和處理形式模型7/22/20233課程目的和基本要求

知識掌握正則語言、下文無關(guān)語言的文法、識別模型及其基本性質(zhì)、圖靈機的基本知識能力培養(yǎng)學(xué)生的形式化描述和抽象思維能力使學(xué)生了解和初步掌握“問題、形式化描述、自動化（計算機化）”這一最典型的計算機問題求解思路7/22/20234主要內(nèi)容

語言的文法描述RLRG、FA、RE、RL的性質(zhì)

CFLCFG(CNF、GNF)、PDA、CFL的性質(zhì)

TM基本TM、構(gòu)造技術(shù)、TM的修改CSLCSG、LBA7/22/20235教材及主要參考書目蔣宗禮，姜守旭.形式語言與自動機理論(第2版).北京：清華大學(xué)出版社，2007年蔣宗禮.形式語言與自動機理論教學(xué)參考書(第2版).北京：清華大學(xué)出版社，2007年蔣宗禮，姜守旭.形式語言與自動機理論.北京：清華大學(xué)出版社，2003年JohnE.Hopcroft,RajeevMotwani,JeffreyD.Ullman,IntroductiontoAutomataTheory,Languages,andComputation(2ndEdition),Addison-WesleyPublishingCompany,2001JohnE.Hopcroft,JeffreyD.Ullman.IntroductiontoAutomataTheory,Languages,andComputation.Addison-WesleyPublishingCompany,19797/22/20236第1章

緒論1.1集合的基礎(chǔ)知識

1.1.1集合及其表示集合：一定范圍內(nèi)的、確定的、并且彼此可以區(qū)分的對象匯集在一起形成的整體叫做集合(Set)，簡稱為集(Set)。

元素：集合的成員為該集合的元素(Element)

集合描述形式

基數(shù)集合的分類

7/22/202371.1.2集合之間的關(guān)系

子集如果集合A中的每個元素都是集合B的元素，則稱集合A是集合B的子集(Subset)，集合B是集合A的包集(Container)。記作AB。也可記作BA。AB讀作集合A包含在集合B中；BA讀作集合B包含集合A。如果AB，且x∈B，但xA，則稱A是B的真子集(ProperSubset)，記作AB7/22/202381.1.2集合之間的關(guān)系集合相等如果集合A，B含有的元素完全相同，則稱集合A與集合B相等(Equivalence)，記作A=B。對任意集合A、B、C：⑴A=BiffAB且BA。⑵如果AB，則|A|≤|B|⑶如果AB，則|A|≤|B|。⑷如果A是有窮集，且AB，則|B|>|A|。7/22/202391.1.2集合之間的關(guān)系⑸如果AB，則對x∈A，有x∈B⑹如果AB，則對x∈A，有x∈B并且x∈B，但xA⑺如果AB且BC，則AC⑻如果AB且BC，或者AB且BC，或者AB且BC，則AC⑼如果A=B，則|A|=|B|7/22/2023101.1.3集合的運算

并(Union)

A與B的并(Union)是一個集合，該集合中的元素要么是A的元素，要么是B的元素

A∪B={a|a∈A或者a∈B}A1∪A2∪…∪An={a|i，1≤i≤n，使得a∈Ai}A1∪A2∪…∪An∪…={a|i，i∈N,使得a∈Ai}7/22/202311交(Intersection)

集合A和B中都有的所有元素放在一起構(gòu)成的集合為A與B的交

A∩B={a|a∈A且a∈B}“∩”為交運算符，A∩B讀作A交B如果A∩B=Φ，則稱A與B不相交⑴A∩B=B∩A⑵(A∩B)∩C=A∩(B∩C)⑶A∩A=A7/22/202312交(Intersection)⑷A∩B=AiffAB⑸Φ∩A=Φ⑹|A∩B|≤min{|A|，|B|}⑺A∩(B∪C)=(A∩B)∪(A∩C)⑻A∪(B∩C)=(A∪B)∩(A∪C)⑼A∩(A∪B)=A⑽A∪(A∩B)=A7/22/202313差(Difference)

屬于A，但不屬于B的所有元素組成的集合叫做A與B的差

A-B={a|a∈A且aB}“-”為減(差)運算符，A-B讀作A減B⑴A-A=Φ⑵A-Φ=A⑶A-B≠B-A⑷A-B=AiffA∩B=Φ⑸A∩(B-C)=(A∩B)-(A∩C)⑹|A-B|≤|A|7/22/202314對稱差(SymmetricDifference)

屬于A但不屬于B，屬于B但不屬于A的所有元素組成的集合叫A與B的對稱差A(yù)⊕B={a|a∈A且aB或者aA且a∈B}“⊕”為對稱差運算符。A⊕B讀作A對稱減BA⊕B=(A∪B)-(A∩B)=(A-B)∪(B-A)7/22/202315笛卡爾積(CartesianProduct)

A與B的笛卡爾積(CartesianProduct)是一個集合，該集合是由所有這樣的有序?qū)?a，b)組成的：其中a∈A，b∈BA×B={(a，b)|a∈A&b∈B}“×”為笛卡爾乘運算符。A×B讀作A叉乘B⑴A×B≠B×A⑵(A×B)×C≠A×(B×C)⑶A×A≠A⑷A×Φ=Φ7/22/202316笛卡爾積(CartesianProduct)⑸A×(B∪C)=(A×B)∪(A×C)⑹(B∪C)×A=(B×A)∪(A×C)⑺A×(B∩C)=(A×B)∩(A×C)⑻(B∩C)×A=(B×A)∩(C×A)⑼A×(B-C)=(A×B)-(A×C)⑽(B-C)×A=(B×A)-(C×A)⑾當(dāng)A、B為有窮集時，|A×B|=|A|*|B|

7/22/202317冪集(PowerSet)

A冪集(PowerSet)是一個集合，該集合是由A的所有子集組成的，記作2A

2A={B|BA}

2A讀作A的冪集7/22/202318冪集(PowerSet)⑴

Φ∈2A⑵

Φ2A⑶

Φ2A⑷2Φ={Φ}⑸A∈2A⑹

如果A是有窮集，則|2A|=2|A|⑺2A∩B=2A∩2B⑻

如果AB，則2A2B

7/22/202319補集(ComplementarySet)

A是論域U上的一個集合，A補集是由U中的、不在A中的所有元素組成的集合7/22/202320補集(ComplementarySet)如果AB，則7/22/2023211.2關(guān)系

1.2.1二元關(guān)系

1.2.2遞歸定義與歸納證明

1.2.3關(guān)系的閉包

7/22/2023221.2.1二元關(guān)系(BinaryRelation)

二元關(guān)系

任意的RA×B，R是A到B的二元關(guān)系(a，b)∈R，也可表示為：aRbA稱為定義域(Domain)，B稱為值域(Range)當(dāng)A=B時，則稱R是A上的二元關(guān)系。二元關(guān)系的性質(zhì)自反(Reflexive)性、反自反(Irreflexive)性、對稱(Symmetric)性、反對稱(Asymmetric)性、傳遞(Transitive)性。7/22/2023231.2.1二元關(guān)系(BinaryRelation)三歧性自反性、對稱性、傳遞性。等價關(guān)系(EquivalenceRelation)

具有三歧性的二元關(guān)系稱為等價關(guān)系

7/22/2023241.2.1二元關(guān)系(BinaryRelation)等價類

(EquivalenceClass)

S的滿足如下要求的劃分：S1、S2、S3、…、Sn…稱為S關(guān)于R的等價劃分，Si稱為等價類⑴S=S1∪S2∪S3∪……∪Sn∪……；⑵如果i≠j，則Si∩Sj=Φ；⑶對任意的i，Si中的任意兩個元素a、b，aRb恒成立；⑷對任意的i，j，i≠j，Si中的任意元素a和Sj中的任意元素b，aRb恒不成立7/22/2023251.2.1二元關(guān)系(BinaryRelation)指數(shù)(Index)

把R將S分成的等價類的個數(shù)稱為是R在S上的指數(shù)。如果R將S分成有窮多個等價類，則稱R具有有窮指數(shù)；如果R將S分成無窮多個等價類，則稱R具有無窮指數(shù)給定集合S上的一個等價關(guān)系R，R就確定了S的一個等價分類，當(dāng)給定另一個不同的等價關(guān)系時，它會確定S的一個新的等價分類7/22/2023261.2.1二元關(guān)系(BinaryRelation)關(guān)系的合成

(Composition)

設(shè)R1A×B是A到B的關(guān)系、R2B×C是B到C的關(guān)系，R1與R2的合成R1R2是A到C的關(guān)系：R1R2={(a，c)|(a，b)∈R1且(b，c)∈R2

7/22/2023271.2.1二元關(guān)系(BinaryRelation)⑴R1R2≠R2R1⑵(R1R2)R3=R1(R2R3) (結(jié)合率)⑶(R1∪R2)R3=R1R3∪R2R3 (右分配率)⑷R3(R1∪R2)=R3R1∪R3R2 (左分配率)⑸(R1∩R2)R3R1R3∩R2R3⑹R3(R1∩R2)R3R1∩R3R27/22/2023281.2.1二元關(guān)系(BinaryRelation)關(guān)系這一個概念用來反映對象——集合元素之間的聯(lián)系和性質(zhì)二元關(guān)系則是反映兩個元素之間的關(guān)系，包括某個元素的某種屬性。對二元關(guān)系的性質(zhì)，要強調(diào)全稱量詞是對什么樣的范圍而言的。

7/22/2023291.2.2遞歸定義與歸納證明遞歸定義(RecursiveDefinition)又稱為歸納定義(InductiveDefinition)，它來定義一個集合集合的遞歸定義由三部分組成基礎(chǔ)(Basis)：用來定義該集合的最基本的元素歸納(Induction)：指出用集合中的元素來構(gòu)造集合的新元素的規(guī)則極小性限定：指出一個對象是所定義集合中的元素的充要條件是它可以通過有限次的使用基礎(chǔ)和歸納條款中所給的規(guī)定構(gòu)造出來7/22/2023301.2.3遞歸定義與歸納證明歸納證明與遞歸定義相對應(yīng)歸納證明方法包括三大步基礎(chǔ)(Basis)：證明最基本元素具有相應(yīng)性質(zhì)歸納(Induction)：證明如果某些元素具有相應(yīng)性質(zhì)，則根據(jù)這些元素用所規(guī)定的方法得到的新元素也具有相應(yīng)的性質(zhì)。根據(jù)歸納法原理，所有的元素具有相應(yīng)的性質(zhì)

7/22/2023311.2.3遞歸定義與歸納證明定義1-17

設(shè)R是S上的關(guān)系，我們遞歸地定義Rn的冪：⑴R0={(a，a)|a∈S}⑵Ri=Ri-1R i=1,2,3,4,5,……

7/22/2023321.2.3遞歸定義與歸納證明例1-17著名的斐波那契(Fibonacci)數(shù)的定義

⑴基礎(chǔ)：0是第一個斐波那契數(shù)，1第二個斐波那契數(shù)；⑵歸納：如果n是第i個斐波那契數(shù)，m是第i+1個斐波那契數(shù)，則n+m是第i+2個斐波那契數(shù)，這里i為大于等于1的正整數(shù)。⑶只有滿足(1)和(2)的數(shù)才是斐波那契數(shù)0，1，1，2，3，5，8，13，21，34，55，……

7/22/2023331.2.3遞歸定義與歸納證明例1-18算術(shù)表達式⑴基礎(chǔ)：常數(shù)是算術(shù)表達式，變量是算術(shù)表達式；⑵歸納：如果E1、E2是表達式，則+E1、-E1、E1+E2、E1-E2

、E1*E2

、E1/E2、E1**E2、Fun(E1)是算術(shù)表達式。其中Fun為函數(shù)名。⑶只有滿足(1)和(2)的才是算術(shù)表達式。

7/22/2023341.2.3遞歸定義與歸納證明例1-19

對有窮集合A，證明|2A|=2|A|。證明： 設(shè)A為一個有窮集合,施歸納于|A|：⑴基礎(chǔ)：當(dāng)|A|=0時,|2A|=|{Φ}|=1。⑵歸納：假設(shè)|A|=n時結(jié)論成立，這里n≥0，往證當(dāng)|A|=n+1時結(jié)論成立

2A=2B∪{C∪{a}|C∈2B}

2B∩{C∪{a}|C∈2B}=Φ

7/22/2023351.2.3遞歸定義與歸納證明

|2A|=|2B∪{C∪{a}|C∈2B}| =|2B|+|{C∪{a}|C∈2B}| =|2B|+|2B| =2*|2B| =2*2|B| =2|B|+1 =2|A|⑶由歸納法原理，結(jié)論對任意有窮集合成立。7/22/2023361.2.3遞歸定義與歸納證明例1-20

表達式的前綴形式是指將運算符寫在前面，后跟相應(yīng)的運算對象。如：+E1的前綴形式為+E1，E1+E2的前綴形式為+E1E2

，E1*E2的前綴形式為*E1E2，

E1**E2的前綴形式為**E1，F(xiàn)un(E1)的前綴形式為FunE1證明例1-18所定義的表達式可以用這里定義的前綴形式表示

7/22/2023371.2.3遞歸定義與歸納證明遞歸定義給出的概念有利于歸納證明。在計算機科學(xué)與技術(shù)學(xué)科中，有許多問題可以用遞歸定義描述或者用歸納方法進行證明，而且在許多時候，這樣做會帶來許多方便

主要是掌握遞歸定義與歸納證明的敘述格式

7/22/2023381.2.3關(guān)系的閉包

閉包(Closure)

設(shè)P是關(guān)于關(guān)系的性質(zhì)的集合，關(guān)系R的P閉包(Closure)是包含R并且具有P中所有性質(zhì)的最小關(guān)系

正閉包(PositiveClosure)

RR+如果(a，b)，(b，c)∈R+

則(a，c)∈R+除(1)、(2)外，R+不再含有其它任何元素

7/22/2023391.2.3關(guān)系的閉包可以證明，對任意二元關(guān)系R，R+=R∪R2∪R3∪R4∪……R+具有傳遞性R+傳遞閉包(TransitiveClosure)

而且當(dāng)S為有窮集時：R+=R∪R2∪R3∪……∪R|S|7/22/2023401.2.3關(guān)系的閉包克林閉包(KleeneClosure)R*

(1)R0R*,RR*⑵如果(a，b)，(b，c)∈R*

則(a，c)∈R*⑶除(1)、(2)外，R*不再含有其它任何元素

R*具有自反性、傳遞性R*有叫自反傳遞閉包(ReflexiveandTransitiveClosure)7/22/2023411.2.3關(guān)系的閉包可以證明，對任意二元關(guān)系R，R*=R0∪R+R*=R0∪R∪R2∪R3∪R4∪…而且當(dāng)S為有窮集時：R*=R0∪R∪R2∪R3∪……∪R|S|

7/22/2023421.2.3關(guān)系的閉包R1、R2是S上的兩個二元關(guān)系

⑴Φ+=Φ⑶(R1+)+=R1+⑷(R1*)*=R1*⑸R1+∪R2+(R1∪R2)+⑹R1*∪R2*(R1∪R2)*

7/22/2023431.3圖數(shù)學(xué)家歐拉(L.Euler)解決著名的哥尼斯堡七橋直觀地，圖是由一些點和一些連接兩點的邊組成。含無方向的邊的圖為無向圖，含帶有方向的邊的圖為有向圖

7/22/2023441.3.1無向圖無向圖(UndirectedGraph)

設(shè)V是一個非空的有窮集合，EV×V，G=(V，E)稱為無向圖(UndirectedGraph)。其中V中的元素稱為頂點(Vertex或Node)，V稱為頂點集，E中的元素稱為無向邊(UndirectedEdge)，E為無向邊集。圖表示V中稱為頂點v的元素用標(biāo)記為v的小圈表示，E中的元素(v1，v2)用標(biāo)記為v1，v2的頂點之間的連線表示。

7/22/2023451.3.1無向圖路(Path)如果對于0≤i≤k-1，k≥1，均有(vi，vi+1)∈E，則稱v0，v1，…，vk是G=(V，E)的一條長為k的路回路或圈(Cycle)當(dāng)路v0，v1，…，vk中v0=vk時，v0，v1，…，vk叫做一個回路或圈(Cycle)7/22/2023461.3.1無向圖頂點的度數(shù)

對于v∈V，|{w|(v，w)∈E}|稱為無向圖G=(V，E)的頂點v的度數(shù)，記作deg(v)。對于任何一個圖，圖中所有頂點的度數(shù)之和為圖中邊的2倍。

7/22/202347deg(v1)=3；deg(v2)=3；deg(v3)=4；deg(v4)=3；deg(v5)=3deg(v1)+deg(v2)+deg(v3)+deg(v4)+deg(v5)=167/22/2023481.3.1無向圖連通圖

如果對于v，w∈V，v≠w，v與w之間至少有一條路存在，則稱G=(V，E)是連通圖。

圖G是連通的充要條件是G中存在一條包含圖的所有頂點的路

7/22/2023491.3.2有向圖有向圖(DirectedGraph)

G=(V，E)V：頂點(Vertex或Node)集(v1，v2)∈E：頂點v1到頂點v2的有向邊(DirectedEdge)，或弧(Arc)，v1稱為前導(dǎo)(Predecessor)，v2稱為后繼(Successor)有向路(DirectedPath)

如果對于0≤i≤k-1，k≥1，均有(vi，vi+1)∈E，則稱v0，v1，…，vk是G的一條長為k的有向路

7/22/2023501.3.2有向圖有向回路或有向圈(DirectedCycle)

對于0≤i≤k-1，k≥1，均有(vi，vi+1)∈E，且v0=vk，則稱v0，v1，…，vk是G的一條長為k的有向路為一個有向回路有向回路又叫有向圈

有向圖的圖表示圖G的圖表示是滿足下列條件的“圖”：其中V中稱為頂點v的元素用標(biāo)記為v的小圈表示，E中的元素(v1，v2)用從標(biāo)記為v1的頂點到標(biāo)記為v2的頂點的弧表示7/22/2023511.3.2有向圖頂點的度數(shù)

入度(數(shù))：ideg(v)=|{w|(w，v)∈E}|

出度(數(shù))：odeg(v)=|{w|(v，w)∈E}|

對于任何一個有向圖，圖中所有頂點的入度之和與圖中所有頂點的出度之和正好是圖中邊的個數(shù)

7/22/202352兩個不同的有向圖7/22/2023531.3.3樹滿足如下條件的有向圖G=(V，E)稱為一棵(有序、有向)樹(Tree)：

根(Root)

v：沒有前導(dǎo)，且v到樹中其它頂點均有一條有向路每個非根頂點有且僅有一個前導(dǎo)每個頂點的后繼按其拓撲關(guān)系從左到右排序

7/22/2023541.3.3樹樹的基本概念

(1)

頂點也可以成為結(jié)點(2)

結(jié)點的前導(dǎo)為該結(jié)點的父親(父結(jié)點Father)(3)

結(jié)點的后繼為它的兒子(Son)(4)

如果樹中有一條從結(jié)點v1到結(jié)點v2的路，則稱v1是v2的祖先(Ancestor),v2是v1的后代(Descendant)(5)

無兒子的頂點叫做葉子(Leaf)(6)

非葉結(jié)點叫做中間結(jié)點(Interior)7/22/2023551.3.3樹樹的層

根處在樹的第1層(Level)

如果結(jié)點v處在第i層(i≥1)，則v的兒子處在第i+1層

樹的最大層號叫做該樹的高度(Height)

7/22/2023561.3.3樹二元樹

如果對于v∈V，v最多只有2個兒子，則稱G=(V，E)為二元樹(BinaryTree)

對一棵二元樹，它的第n層最多有2n-1個結(jié)點。一棵n層二元樹最多有個2n-1葉子

7/22/2023571.4語言？什么是語言

“學(xué)大一生是個我”“我是一個大學(xué)生”語言是一定的群體用來進行交流的工具

必須有著一系列的生成規(guī)則、理解(語義)規(guī)則

7/22/2023581.4.1什么是語言7/22/2023591.4.1什么是語言斯大林：從強調(diào)語言的作用出發(fā)，把語言定義為“為廣大的人群所理解的字和組合這些字的方法”

語言學(xué)家韋波斯特(Webster)：為相當(dāng)大的團體的人所懂得并使用的字和組合這些字的方法的統(tǒng)一體

要想對語言的性質(zhì)進行研究，用這些定義來建立語言的數(shù)學(xué)模型是不夠精確的。必須有更形式化的定義

7/22/2023601.4.2形式語言與自動機理論的產(chǎn)生與作用語言學(xué)家喬姆斯基，畢業(yè)于賓西法尼亞大學(xué)，最初從產(chǎn)生語言的角度研究語言。1956年，他將語言L定義為一個字母表∑中的字母組成的一些串的集合：L∑*。

字母表上按照一定的規(guī)則定義一個文法(Grammar)，該文法所能產(chǎn)生的所有句子組成的集合就是該文法產(chǎn)生的語言

1959年，喬姆斯基根據(jù)產(chǎn)生語言文法的特性，將語言劃分成3大類

7/22/2023611.4.2形式語言與自動機理論的產(chǎn)生與作用1951年到1956年，克林(Kleene)在研究神經(jīng)細胞中，建立了識別語言的系統(tǒng)——有窮狀態(tài)自動機

1959年，喬姆斯基發(fā)現(xiàn)文法和自動機分別從生成和識別的角度去表達語言，而且證明了文法與自動機的等價性，這一成果被認為是將形式語言置于了數(shù)學(xué)的光芒之下，使得形式語言真正誕生了

7/22/2023621.4.2形式語言與自動機理論的產(chǎn)生與作用20世紀50年代，巴科斯范式(BackusNourForm或BackusNormalForm，簡記為BNF)實現(xiàn)了對高級語言ALGOL-60的成功描述。這一成功，使得形式語言在20世紀60年代得到了大力的發(fā)展。尤其是上下文無關(guān)文法被作為計算機程序設(shè)計語言的文法的最佳近似描述得到了較為深入的研究

相應(yīng)的理論用于其它方面

7/22/2023631.4.2形式語言與自動機理論的產(chǎn)生與作用形式語言與自動機理論在計算機科學(xué)與技術(shù)學(xué)科的人才的計算思維的培養(yǎng)中占有極其重要的地位

計算學(xué)科的主題：“什么能被有效地自動化”。

7/22/2023641.4.2形式語言與自動機理論的產(chǎn)生與作用計算機科學(xué)與技術(shù)學(xué)科人才專業(yè)能力構(gòu)成

“計算思維能力”——抽象思維能力、邏輯思維能力

算法設(shè)計與分析能力程序設(shè)計與實現(xiàn)能力計算機系統(tǒng)的認知、分析、設(shè)計和應(yīng)用能力

7/22/2023651.4.2形式語言與自動機理論的產(chǎn)生與作用7/22/2023661.4.2形式語言與自動機理論的產(chǎn)生與作用考慮的對象的不同，所需要的思維方式和能力就不同，通過這一系統(tǒng)的教育，在不斷升華的過程中，逐漸地培養(yǎng)出了學(xué)生的抽象思維能力和對邏輯思維方法的掌握。創(chuàng)新意識的建立和創(chuàng)新能力的培養(yǎng)也在這個教育過程中循序漸進地進行著內(nèi)容用于后續(xù)課程和今后的研究工作是進行思維訓(xùn)練的最佳知識載體

是一個優(yōu)秀的計算機科學(xué)工作者必修的一門課程

7/22/2023671.4.3基本概念對語言研究的三個方面

表示(Representation)——

無窮語言的表示

有窮描述(FiniteDescription)——研究的語言要么是有窮的，要么是可數(shù)無窮的，這里主要研究可數(shù)無窮語言的有窮描述

結(jié)構(gòu)(Structure)——語言的結(jié)構(gòu)特征

7/22/2023681.4.3基本概念字母表(Alphabet)是一個非空有窮集合，字母表中的元素稱為該字母表的一個字母(Letter)。又叫做符號(Symbol)、或者字符(Character)非空性有窮性例{a，b，c，d}{a，b，c，…，z}{0,1}7/22/2023691.4.3基本概念字符的兩個特性

整體性(Monolith)，也叫不可分性

可辨認性(Distinguishable)，也叫可區(qū)分性

例（續(xù)）{a，a′，b，b′}{aa，ab，bb}{∞，∧，∨，≥，≤}7/22/2023701.4.3基本概念字母表的乘積(Product)∑1∑2={ab|a∈∑1，b∈∑2}例{0,1}{0,1}={00，01，10，11}{0,1}{a，b，c，d}={0a，0b，0c，0d，1a，1b，1c，1d}{a，b，c，d}{0,1}={a0，a1，b0，b1，c0，c1，d0，d1}{aa，ab，bb}{0,1}={aa0，aa1，ab0，ab1，bb0，bb1}7/22/2023711.4.3基本概念字母表∑的n次冪

∑0={ε}∑n=∑n-1∑

ε是由∑中的0個字符組成的

∑的正閉包

∑+=∑∪∑2∪∑3∪∑4∪…∑的克林閉包∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪…7/22/2023721.4.3基本概念例

{0,1}+={0，1，00，01，10，11，000，001，010，011，100，…}{0,1}*={ε，0，1，00，01，10，11，000，001，010，011，100，…}{a，b，c，d}+={a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，…，aaa，aab，aac，aad，aba，abb，abc，…}{a，b，c，d}*={ε，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，…，aaa，aab，aac，aad，aba，abb，abc,…}7/22/202373

1.4.3基本概念結(jié)論：∑*={x|x是∑中的若干個，包括0個字符，連接而成的一個字符串}∑+={x|x是∑中的至少一個字符連接而成的字符串}7/22/2023741.4.3基本概念句子(Sentence)

∑是一個字母表，x∈∑*，x叫做∑上的一個句子句子相等兩個句子被稱為相等的，如果它們對應(yīng)位置上的字符都對應(yīng)相等別稱字(Word)、(字符、符號)行(Line)、(字符、符號)串(String)

7/22/2023751.4.3基本概念出現(xiàn)(Apperance)x，y∈∑*，a∈∑，句子xay中的a叫做a在該句子中的一個出現(xiàn)當(dāng)x=ε時，a的這個出現(xiàn)為字符串xay的首字符如果a的這個出現(xiàn)是字符串xay的第n個字符，則y的首字符的這個出現(xiàn)是字符串xay的第n+1個字符當(dāng)y=ε時，a的這個出現(xiàn)是字符串xay的尾字符例：abaabb

7/22/2023761.4.3基本概念句子的長度(Length)

x∈∑*，句子x中字符出現(xiàn)的總個數(shù)叫做該句子的長度，記作|x|長度為0的字符串叫空句子，記作ε例

|abaabb|=6|bbaa|=4|ε|=0|bbabaabbbaa|=117/22/2023771.4.3基本概念注意事項ε是一個句子

{ε}≠Φ。這是因為{ε}不是一個空集，它是含有一個空句子ε的集合。|{ε}|=1，而|Φ|=0

7/22/2023781.4.3基本概念并置(Concatenation)

x，y∈∑*，x，y的并置是由串x直接相接串y所組成的。記作xy。并置又叫做連結(jié)

串x的n次冪x0=ε

xn=xn-1x

7/22/2023791.4.3基本概念例

對x=001，y=1101x0=y0=εx4=001001001001y4=1101110111011101對x=0101，y=110110x2=01010101y2=110110110110x4=0101010101010101y4=1101101101101101101101107/22/2023801.4.3基本概念∑*上的并置運算性質(zhì)⑴結(jié)合律：(xy)z=x(yz)；⑵左消去律：如果xy=xz，則y=z；⑶右消去律：如果yx=zx，則y=z；⑷唯一分解性：存在唯一確定的a1，a2，……，an∈∑，使得x=a1a2……an；⑸單位元素：εx=xε=x7/22/2023811.4.3基本概念前綴與后綴

設(shè)x，y，z，w，v∈∑*，且x=yz，w=yv

(1)

y是x的前綴(Prefix)；(2)

如果z≠ε，則y是x的真前綴(ProperPrefix)；(3)

z是x的后綴(Suffix)；(4)

如果y≠ε，則z是x的真后綴(ProperSuffix)。(5)

y是x和w的公共前綴(CommonPrefix)；7/22/2023821.4.3基本概念公共前綴與后綴(6)

如果x和w的任何公共前綴都是y的前綴，則y是x和w的最大公共前綴。(7)

如果x=zy，w=vy，則y是x和w的公共后綴(CommonSuffix)；(8)如果x和w的任何公共后綴都是y的后綴，則y是x和w的最大公共后綴7/22/2023831.4.3基本概念例

字母表∑={a，b}上的句子abaabb的前綴、后綴、真前綴和真后綴如下：前綴：ε，a，ab，aba，abaa，abaab，abaabb真前綴：ε，a，ab，aba，abaa，abaab后綴：ε，b，bb，abb，aabb，baabb，abaabb真后綴：ε，b，bb，abb，aabb，baabb

7/22/2023841.4.3基本概念結(jié)論⑴

x的任意前綴y有唯一的一個后綴z與之對應(yīng)，使得x=yz；反之亦然。⑵

x的任意真前綴y有唯一的一個后綴z與之對應(yīng)，使得x=yz；反之亦然。⑶

|{w|w是x的后綴}|=|{w|w是x的前綴}|。⑷

|{w|w是x的真后綴}|=|{w|w是x的真前綴}|。⑸

{w|w是x的前綴}={w|w是x的真前綴}∪{x}，|{w|w是x的前綴}|=|{w|w是x的真前綴}|+17/22/2023851.4.3基本概念結(jié)論⑹

{w|w是x的后綴}={w|w是x的真后綴}∪{x}，|{w|w是x的后綴}|=|{w|w是x的真后綴}|+1。

⑺

對于任意字符串w，w是自身的前綴，但不是自身的真前綴；w是自身的后綴，但不是自身的真后綴。⑻對于任意字符串w，ε是w的前綴，且是w的真前綴；ε是w的后綴，且是w的真后綴7/22/2023861.4.3基本概念約定

⑴用小寫字母表中較為靠前的字母a，b，c，……表示字母表中的字母；⑵用小寫字母表中較為靠后的字母x，y，z，……表示字母表上的句子；⑶用xT表示x的倒序。例如，如果x=abc，則xT=cba

7/22/2023871.4.3基本概念子串(Substring)

w，x，y，z∈∑*，且w=xyz，則稱y是w的子串公共子串(CommonSubstring)

t，u，v，w，x，y，z∈∑*，且t=uyv，w=xyz，則稱y是t和w的公共子串(CommonSubstring)。如果y1，y2，……，yn是t和w的公共子串，且max{|y1|，|y2|，…，|yn|}=|yj|，則稱yj是t和w的最大公共子串

兩個串的最大公共子串并不一定是唯一的

7/22/2023881.4.3基本概念語言(Language)

L∑*，L稱為字母表∑上的一個語言(Language)，x∈L，x叫做L的一個句子

例：{0，1}上的不同語言

{00，11}，{0，1}{0，1，00，11}，{0，1，00，11，01，10}{00，11}*，{01，10}*，{00，01，10，11}*，{0}{0，1}*{1}，{0，1}*{111}{0，1}*7/22/2023891.4.3基本概念語言的乘積(Product)L1∑1*，L2∑2*，語言L1與L2的乘積是一個語言，該語言定義為：L1L2={xy|x∈L1，y∈L2}是字母表∑1∪∑2上的語言。

7/22/2023901.4.3基本概念例⑴

L1={0，1}⑵L2={00，01，10，11}⑶L3={0，1，00，01，10，11，000，…}=∑+⑷L4={ε，0，1，00，01，10，11，000，…}=∑*⑸L5={0n|n≥1}⑹L6={0n1n|n≥1}⑺L7={1n|n≥1}⑻L8={0n1m|n，m≥1}⑼L9={0n1n0n|n≥1}⑽L10={0n1m0k|n，m，k≥1}⑾L11={x|x∈∑+且x中0和1的個數(shù)相同}7/22/2023911.4.3基本概念上述幾個語言的部分特點及相互關(guān)系

上述所有語言都是L4的子集(子語言)；L1，L2是有窮語言；其它為無窮語言；其中L1是∑上的所有長度為1的句子組成的語言，L2是∑上的所有長度為2的句子組成的語言；L3，L4分別是∑的正閉包和克林閉包；L5L7≠L6，但L5L7=L8；同樣L9≠L10，但是我們有：L6L5L7，L9L10

7/22/2023921.4.3基本概念L6={0n1n|n≥1}中的句子中的0和1的個數(shù)是相同的，并且所有的0在所有的1的前面，L11={x|x∈∑+且x中0和1的個數(shù)相同}中的句子中雖然保持著0的個數(shù)和1的個數(shù)相等，但它并沒要求所有的0在所有的1的前面。例如，0101，1100∈L11，但是0101L6，1100L6。而對x∈L6，有x∈L11。所以，L6

L117/22/2023931.4.3基本概念L1L12，L2L12L5L12，L6L12L7L12，L8L12L9L12，L10L12L1L10，L2L10L5L10，L6L10L7L10，L8L10L9L10，L10L127/22/2023941.4.3基本概念例

⑴{x|x=xT，x∈∑}⑵{xxT|x∈∑+}⑶{xxT|x∈∑*}⑷{xwxT|x，w∈∑+}⑸{xxTw|x，w∈∑+}

7/22/2023951.4.3基本概念冪L∈∑*，L的n次冪是一個語言，該語言定義為

⑴當(dāng)n=0是，Ln={ε}

⑵當(dāng)n≥1時，Ln=Ln-1L

正閉包L+=L∪L2∪L3∪L4∪…

克林閉包L*=L0∪L∪L2∪L3∪L4∪…

7/22/2023961.5小結(jié)本章簡單敘述了一些基礎(chǔ)知識，一方面，希望讀者通過對本章的閱讀，熟悉集合、關(guān)系、圖、形式語言等相關(guān)的一些基本知識點，為以后各章學(xué)習(xí)作適當(dāng)?shù)臏?zhǔn)備。另一方面，也使讀者熟悉本書中一些符號的意義

7/22/2023971.5小結(jié)(1)

集合：集合的表示、集合之間的關(guān)系、集合的基本運算。(2)

關(guān)系：主要介紹了二元關(guān)系相關(guān)的內(nèi)容。包括等價關(guān)系、等價分類、關(guān)系合成、關(guān)系閉包。(3)

遞歸定義與歸納證明。7/22/2023981.5小結(jié)(4)

圖：無向圖、有向圖、樹的基本概念。(5)

語言與形式語言：自然語言的描述，形式語言和自動機理論的出現(xiàn)，形式語言和自動機理論對計算機科學(xué)與技術(shù)學(xué)科人才能力培養(yǎng)的作用(6)

基本概念：字母表、字母、句子、字母表上的語言、語言的基本運算7/22/202399第2章文法對任何語言L，有一個字母表∑，使得L∑*

L的具體組成結(jié)構(gòu)是什么樣的？一個給定的字符串是否為一個給定語言的句子?如果不是，它在結(jié)構(gòu)的什么地方出了錯？進一步地，這個錯誤是什么樣的錯？如何更正？……。這些問題對有窮語言來說，比較容易解決這些問題對無窮語言來說，不太容易解決語言的有窮描述7/22/2023100第2章文法

主要內(nèi)容文法的直觀意義與形式定義，推導(dǎo)、文法產(chǎn)生的語言、句子、句型；喬姆斯基體系，左線性文法、右線性文法，文法的推導(dǎo)與歸約；空語句。重點文法、推導(dǎo)、歸約、模型的等價性證明。難點形式化的概念，文法的構(gòu)造

7/22/20231012.1啟示文法的概念最早是由語言學(xué)家們在研究自然語言理解中完成形式化

歸納如下句子的描述⑴

哈爾濱是美麗的城市。⑵

北京是祖國的首都。⑶

集合是數(shù)學(xué)的基礎(chǔ)。⑷

形式語言是很抽象的。⑸

教育走在社會發(fā)展的前面。⑹

中國進入WTO。7/22/20231022.1啟示6個句子的主體結(jié)構(gòu)

<名詞短語><動詞短語><句號>

<名詞短語>={哈爾濱，北京，集合，形式語言，教育，中國}<動詞短語>={是美麗的城市，是祖國的首都，是數(shù)學(xué)的基礎(chǔ)，是很抽象的，走在社會發(fā)展的前面，進入WTO}

<句號>={。}

7/22/20231032.1啟示<動詞短語>可以是<動詞><形容詞短語>

或者<動詞><名詞短語>

<名詞短語>={北京、哈爾濱、形式語言、中國、教育、集合、WTO、美麗的城市、祖國的首都、數(shù)學(xué)的基礎(chǔ)、社會發(fā)展的前面}

<動詞>={是、走在、進入}<形容詞短語>={很抽象的}把<名詞短語><動詞短語><句號>取名為<句子>

7/22/20231042.1啟示7/22/20231052.1啟示表示成αβ形式<句子><名詞短語><動詞短語><句號><動詞短語><動詞><形容詞短語><動詞短語><動詞><名詞短語><動詞>是7/22/20231062.1啟示<動詞>走在<動詞>進入<形容詞短語>很抽象的<名詞短語>北京<名詞短語>哈爾濱<名詞短語>形式語言7/22/20231072.1啟示<名詞短語>中國<名詞短語>教育<名詞短語>集合<名詞短語>WTO<名詞短語>美麗的城市<名詞短語>祖國的首都<名詞短語>數(shù)學(xué)的基礎(chǔ)<名詞短語>社會發(fā)展的前面<句號>。7/22/20231082.1啟示表示一個語言，需要4種東西形如<名詞短語>的“符號”它們表示相應(yīng)語言結(jié)構(gòu)中某個位置上可以出現(xiàn)的一些內(nèi)容。每個“符號”對應(yīng)的是一個集合，在該語言的一個具體句子中，句子的這個位置上能且僅能出現(xiàn)相應(yīng)集合中的某個元素。所以，這種“符號”代表的是一個語法范疇

<句子>所有的“規(guī)則”，都是為了說明<句子>的結(jié)構(gòu)而存在，相當(dāng)于說，定義的就是<句子>7/22/20231092.1啟示3.

形如北京的“符號”它們是所定義語言的合法句子中將出現(xiàn)的“符號”。僅僅表示自身，稱為終極符號

4.所有的“規(guī)則”都呈αβ的形式在產(chǎn)生語言的句子中被使用，稱這些“規(guī)則”為產(chǎn)生式

7/22/20231102.2形式定義文法(Grammar)

G=(V，T，P，S)

V——為變量(Variable)的非空有窮集。A∈V，A叫做一個語法變量(SyntacticVariable)，簡稱為變量，也可叫做非終極符號(Nonterminal)。它表示一個語法范疇(SyntacticCategory)。所以，本文中有時候又稱之為語法范疇

7/22/20231112.2形式定義T——為終極符(Terminal)的非空有窮集。a∈T，a叫做終極符。由于V中變量表示語法范疇，T中的字符是語言的句子中出現(xiàn)的字符，所以，有V∩T=Φ

S——S∈V，為文法G的開始符號(StartSymbol)

7/22/20231122.2形式定義P——為產(chǎn)生式(Production)的非空有窮集合。P中的元素均具有形式αβ，被稱為產(chǎn)生式，讀作：α定義為β。其中α∈(V∪T)+，且α中至少有V中元素的一個出現(xiàn)。β∈(V∪T)*。α稱為產(chǎn)生式αβ的左部，β稱為產(chǎn)生式αβ的右部。產(chǎn)生式又叫做定義式或者語法規(guī)則

7/22/20231132.2形式定義例2-1以下四元組都是文法

⑴({A}，{0，1}，{A01，A0A1，A1A0}，A)⑵({A}，{0，1}，{A0，A0A}，A)⑶({A，B}，{0，1}，{A01，A0A1，A1A0，BAB，B0}，A)⑷({A，B}，{0，1}，{A0，A1，A0A，A1A}，A)7/22/20231142.2形式定義⑸({S，A，B，C，D},{a，b，c，d,#}，{SABCD，Sabc#，AaaA，ABaabbB，BCbbccC，cCcccC，CDccd#，CDd#，CD#d}，S)⑹({S},{a，b}，{S00S，S11S，S00，S11}，S)

7/22/20231152.2形式定義約定

⑴對一組有相同左部的產(chǎn)生式αβ1，αβ2……，αβn可以簡單地記為：αβ1|β2|……|βn讀作：α定義為β1，或者β2，……，或者βn。并且稱它們?yōu)棣廉a(chǎn)生式。β1，β2，……，βn稱為候選式(Candidate)

7/22/20231162.2形式定義⑵使用符號英文字母表較為前面的大寫字母，如A，B，C，……表示語法變量；英文字母表較為前面的小寫字母，如a，b，c，……表示終極符號；英文字母表較為后面的大寫字母，如X，Y，Z，……表示該符號是語法變量或者終極符號；英文字母表較為后面的小寫字母，如x，y，z，……表示由終極符號組成的行；希臘字母α，β，γ……表示由語法變量和終極符號組成的行7/22/20231172.2形式定義例2-2

四元組是否滿足文法的要求({A，B，C，E}，{a，b，c}，{SABC|abc，De|a，F(xiàn)Bc，AA，E

abc|ε}，S)4種修改({A，B，C，E，S，D，F(xiàn)}，{a，b，c，e}，{SABC|abc，De|a，F(xiàn)Bc，AA，E

abc|ε}，S)({A，B，C，E，S}，{a，b，c}，{SABC|abc，AA，E

abc|ε}，S)({A，B，C，E}，{a，b，c}，{AA，E

abc|ε}，A)({A，B，C，E}，{a，b，c}，{AA，E

abc|ε}，E)7/22/20231182.2形式定義推導(dǎo)(Derivation)

設(shè)G=(V，T，P，S)是一個文法，如果αβ∈P，γ，δ∈(V∪T)*，則稱γαδ在G中直接推導(dǎo)出γβδγαδGγβδ讀作：γαδ在文法G中直接推導(dǎo)出γβδ?！爸苯油茖?dǎo)”可以簡稱為推導(dǎo)(Derivation)也稱推導(dǎo)為派生

7/22/20231192.2形式定義歸約(Reduction)

γαδGγβδ稱γβδ在文法G中直接歸約成γαδ。在不特別強調(diào)歸約的直接性時，“直接歸約”可以簡稱為歸約

7/22/20231202.2形式定義1．

推導(dǎo)與歸約表達的意思的異同。2．

推導(dǎo)與歸約和產(chǎn)生式不一樣。所以，G和所表達的意思不一樣。3．

推導(dǎo)與歸約是一一對應(yīng)的。4．

推導(dǎo)與歸約的作用。7/22/20231212.2形式定義G、G+、G*當(dāng)成(V∪T)*上的二元關(guān)系

αGnβ：表示α在G中經(jīng)過n步推導(dǎo)出β；β在G中經(jīng)過n步歸約成α。即，存在α1，α2，……，αn-1∈(V∪T)*使得αGα1，α1Gα2，……，αn-1Gβ

當(dāng)n=0時，有α=β。即αG0α

αG+β：表示α在G中經(jīng)過至少1步推導(dǎo)出β；β在G中經(jīng)過至少1步歸約成α

7/22/20231222.2形式定義4.αG*β：表示α在G中經(jīng)過若干步推導(dǎo)出β；β在G中經(jīng)過若干步歸約成α

分別用 、+、*、n代替

G、G+、G*、Gn7/22/20231232.2形式定義例2-4

設(shè)G=({A}，{a}，{Aa|aA}，A)A

aA

使用產(chǎn)生式AaAaaA

使用產(chǎn)生式AaA

aaaA

使用產(chǎn)生式AaA

aaaaA

使用產(chǎn)生式AaA……a……aA

使用產(chǎn)生式AaAa……aa

使用產(chǎn)生式Aa7/22/20231242.2形式定義A

aA

使用產(chǎn)生式AaAaaA

使用產(chǎn)生式AaAaaaA

使用產(chǎn)生式AaAaaaaA

使用產(chǎn)生式AaA……a……aA

使用產(chǎn)生式AaAa……aaA 使用產(chǎn)生式AaA7/22/20231252.2形式定義AAaaAAA

AAaaAaAA

使用產(chǎn)生式AaA

AaAaaAaAA

使用產(chǎn)生式AaA

AaAaaAaaA

使用產(chǎn)生式Aa

aaAaaAaaA

使用產(chǎn)生式Aa

aaAaaAaaa

使用產(chǎn)生式Aa

aaaAaaAaaa

使用產(chǎn)生式AaA

aaaaaaAaaa

使用產(chǎn)生式Aa

aaaaaaaaaa

使用產(chǎn)生式Aa

7/22/20231262.2形式定義例2-2-5

設(shè)G=({S，A，B}，{0，1}，{SA|AB，A0|0A，B1|11}，S)

對于n≥1，

An0n

首先連續(xù)n-1次使用產(chǎn)生式A0A，最后使用產(chǎn)生式A0；

An0nA 連續(xù)n次使用產(chǎn)生式A0A；

B1 使用產(chǎn)生式B1；

B11 使用產(chǎn)生式B11

7/22/20231272.2形式定義語法范疇A代表的集合L(A)={0，00，000，0000，……}={0n|n≥1}；語法范疇B代表的集合L(B)={1，11}語法范疇S代表的集合L(S)=L(A)∪L(A)L(B)={0，00，000，0000，…}∪{0，00，000，0000，…}{1，11}={0，00，000，0000，…}∪∪{01，001，0001，00001，…}∪∪{011，0011，00011，000011，…}

7/22/20231282.2形式定義例2-6

設(shè)G=({A}，{0，1}，{A01，A0A1}，A)，

An0nA1n n≥00nA1n

0n+1A1n+1 n≥0 0nA1n

0n+11n+1 n≥0 0nA1n

i0n+iA1n+i n≥0，i≥0 0nA1n

i0n+i1n+I n≥0，i≥0 0nA1n

*0mA1m n≥0，m≥n 0nA1n

+0m1m n≥0，m≥n+1 0nA1n

+0mA1m n≥0，m≥n+1 0nA1n

+0m1m n≥0，m≥n+1

7/22/20231292.2形式定義幾點結(jié)論對任意的x∈∑+，我們要使語法范疇D代表的集合為{xn|n≥0}，可用產(chǎn)生式組{Dε|xD}來實現(xiàn)

對任意的x，y∈∑+，我們要使語法范疇D代表的集合為{xnyn|n≥1}，可用產(chǎn)生式組{Dxy|xDy}來實現(xiàn)

對任意的x，y∈∑+，我們要使語法范疇D代表的集合為{xnyn|n≥0}，可用產(chǎn)生式組{Dε|xDy}來實現(xiàn)

7/22/20231302.2形式定義語言(Language)

L(G)={w|w∈T*且S*w}

句子(Sentence)w∈L(G)，w稱為G產(chǎn)生的一個句子句型(SententialForm)G=(V，T，P，S)，對于α∈(V∪T)*，如果S*

α，則稱α是G產(chǎn)生的一個句型7/22/20231312.2形式定義句子w是從S開始，在G中可以推導(dǎo)出來的終極符號行，它不含語法變量

句型α是從S開始，在G中可以推導(dǎo)出來的符號行，它可能含有語法變量

例2-7

給定文法G=({S，A，B，C，D},{a，b，c，d,#}，{SABCD|abc#，AaaA，ABaabbB，BCbbccC，cCcccC，CDccd#，CDd#，CD#d}，S)

7/22/20231322.2形式定義S

ABCD 使用產(chǎn)生式SABCD，aaABCD 使用產(chǎn)生式AaaA，aaaaABCD 使用產(chǎn)生式AaaA，aaaaaabbBCD 使用產(chǎn)生式ABaabbB，aaaaaabbbbccCD 使用產(chǎn)生式BCbbccC，aaaaaabbbbccccCD

使用產(chǎn)生式cCcccC，aaaaaabbbbcccc#d 使用產(chǎn)生式CD#d

7/22/20231332.2形式定義S

ABCD 使用產(chǎn)生式SABCD，AbbccCD

使用產(chǎn)生式BCbbccC，aaAbbccCD

使用產(chǎn)生式AaaA，aaAbbccccd# 使用產(chǎn)生式CDccd#，aaaaAbbccccd# 使用產(chǎn)生式AaaA，aaaaaaAbbccccd# 使用產(chǎn)生式AaaA，aaaaaaaaAbbccccd# 使用產(chǎn)生式AaaA7/22/20231342.2形式定義例2-8

構(gòu)造產(chǎn)生標(biāo)識符的文法

G=({<標(biāo)識符>，<大寫字母>，<小寫字母>，<阿拉伯?dāng)?shù)字>}，{0，1，…，9，A，B，C，…，Z，a，b，c，…，z}，P,<標(biāo)識符>)P={<標(biāo)識符><大寫字母>|<小寫字母>，<標(biāo)識符><標(biāo)識符><大寫字母>|<標(biāo)識符><小寫字母>|<標(biāo)識符><阿拉伯?dāng)?shù)字>，<大寫字母>A|B|C|D|E|F|G|H|I|J|K|L|M|N|O，<大寫字母>P|Q|R|S|T|U|V|W|X|Y|Z，<小寫字母>a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z，<阿拉伯?dāng)?shù)字>0|1|2|3|4|5|6|7|8|9}

7/22/20231352.2形式定義G′=({<標(biāo)識符>，<頭>，<尾>}，{0，1，2，……，9，A，B，C，……，Z，a，b，c，……，z}，P′,<標(biāo)識符>)P′={<標(biāo)識符><頭><尾>，<頭>A|B|C|D|E|F|G|H|I|J|K|L|M|N<頭>O|P|Q|R|S|T|U|V|W|X|Y|Z，<頭>a|b|c|d|e|f|g|h|i|j|k|l|m|n<頭>o|p|q|r|s|t|u|v|w|x|y|z，7/22/20231362.2形式定義<尾>ε|0<尾>|1<尾>|2<尾>|3<尾>|4<尾>|5<尾>,<尾>6<尾>|7<尾>|8<尾>|9<尾>，<尾>A<尾>|B<