形式語(yǔ)言與自動(dòng)化理論-第一章緒論20160919

2023/2/41計(jì)算機(jī)軟件理論基礎(chǔ)

課程目的和基本要求2023/2/42課程性質(zhì)技術(shù)基礎(chǔ)

基礎(chǔ)知識(shí)要求

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

主要特點(diǎn)

抽象和形式化

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

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

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

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

2023/2/45語(yǔ)言的文法描述。RLRG、FA、RE、RL的性質(zhì)。CFLCFG(CNF、GNF)、PDA、CFL的性質(zhì)。

TM基本TM、構(gòu)造技術(shù)、TM的修改。CSLCSG、LBA。教材及主要參考書目2023/2/46蔣宗禮，姜守旭.形式語(yǔ)言與自動(dòng)機(jī)理論.北京：清華大學(xué)出版社，2013年

(第3版）JohnEHopcroft,RajeevMotwani,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation(2ndEdition).Addison-WesleyPublishingCompany,2001JohnEHopcroft,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation.Addison-WesleyPublishingCompany,1979成績(jī)?cè)u(píng)定2023/2/471.

平時(shí)考勤、作業(yè)----40%2.期末考試----60%第1章

緒論2023/2/481.1集合的基礎(chǔ)知識(shí)1.1.1集合及其表示集合：一定范圍內(nèi)的、確定的、并且彼此可以區(qū)分的對(duì)象匯集在一起形成的整體叫做集合(set)，簡(jiǎn)稱為集(set)。

元素：集合的成員為該集合的元素(element)。集合描述形式。

基數(shù)。

集合的分類。

1.1.2集合之間的關(guān)系

2023/2/49子集

如果集合A中的每個(gè)元素都是集合B的元素，則稱集合A是集合B的子集(subset)，集合B是集合A的包集(container)。記作AB。也可記作BA。AB讀作集合A包含在集合B中；BA讀作集合B包含集合A。如果AB，且x∈B，但xA，則稱A是B的真子集(propersubset)，記作AB1.1.2集合之間的關(guān)系2023/2/410集合相等

如果集合A，B含有的元素完全相同，則稱集合A與集合B相等(equivalence)，記作A=B。對(duì)任意集合A、B、C：⑴A=BiffAB且BA。⑵如果AB，則|A|≤|B|。⑶如果AB，則|A|≤|B|。⑷如果A是有窮集，且AB，則|B|>|A|。1.1.2集合之間的關(guān)系2023/2/411⑸如果AB，則對(duì)x∈A，有x∈B。⑹如果AB，則對(duì)x∈A，有x∈B并且x∈B，但xA。⑺如果AB且BC，則AC。⑻如果AB且BC，或者AB且BC，或者AB且BC，則AC。⑼

如果A=B，則|A|=|B|。1.1.3集合的運(yùn)算

2023/2/412并(union)A與B的并(union)是一個(gè)集合，該集合中的元素要么是A的元素，要么是B的元素，記作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}交(intersection)

2023/2/413集合A和B中都有的所有元素放在一起構(gòu)成的集合為A與B的交，記作A∩B。

A∩B={a|a∈A且a∈B}“∩”為交運(yùn)算符，A∩B讀作A交B。如果A∩B=Φ，則稱A與B不相交。⑴A∩B=B∩A。⑵(A∩B)∩C=A∩(B∩C)。⑶A∩A=A。交(INTERSECTION)2023/2/414⑷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)=A。差(difference)

2023/2/415屬于A，但不屬于B的所有元素組成的集合叫做A與B的差，記作A-B。

A-B={a|a∈A且aB}“-”為減(差)運(yùn)算符，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|。對(duì)稱差(symmetricdifference)

2023/2/416屬于A但不屬于B，屬于B但不屬于A的所有元素組成的集合叫A與B的對(duì)稱差，記作A⊕B。

A⊕B={a|a∈A且aB或者aA且a∈B}“⊕”為對(duì)稱差運(yùn)算符。A⊕B讀作A對(duì)稱減B。A⊕B=(A∪B)-(A∩B)=(A-B)∪(B-A)。笛卡兒積(Cartesianproduct)

2023/2/417A與B的笛卡兒積(Cartesianproduct)是一個(gè)集合，該集合是由所有這樣的有序?qū)?a，b)組成的：其中a∈A，b∈B，記作A×B。

A×B={(a，b)|a∈A&b∈B}?！啊痢睘榈芽▋撼诉\(yùn)算符。A×B讀作A叉乘B。⑴

A×B≠B×A。⑵

(A×B)×C≠A×(B×C)。⑶

A×A≠A。⑷

A×Φ=Φ。笛卡兒積(CARTESIANPRODUCT)2023/2/418⑸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)。⑼

A×(B-C)=(A×B)-(A×C)。⑽

(B-C)×A=(B×A)-(C×A)。⑾

當(dāng)A、B為有窮集時(shí)，|A×B|=|A|*|B|。

冪集(powerset)

2023/2/419A冪集(powerset)是一個(gè)集合，該集合是由A的所有子集組成的，記作2A。

2A={B|BA}。

2A讀作A的冪集。冪集(POWERSET)2023/2/420⑴

Φ∈2A。⑵

Φ2A。⑶Φ2A。⑷2Φ={Φ}。⑸A∈2A。⑹如果A是有窮集，則|2A|=2|A|。⑺

2A∩B=2A∩2B。⑻如果AB，則2A2B。

補(bǔ)集(complementaryset)

2023/2/421A是論域U上的一個(gè)集合，A補(bǔ)集是由U中的、不在A中的所有元素組成的集合，記作補(bǔ)集(COMPLEMENTARYSET)2023/2/422如果AB，則。。。。。。1.2關(guān)系

2023/2/423二元關(guān)系

遞歸定義與歸納證明

關(guān)系的閉包

1.2.1二元關(guān)系(binaryrelation)

2023/2/424二元關(guān)系

任意的RA×B，R是A到B的二元關(guān)系。

(a，b)∈R，也可表示為：aRb。

A稱為定義域(domain)，B稱為值域(range)。當(dāng)A=B時(shí)，則稱R是A上的二元關(guān)系。二元關(guān)系的性質(zhì)自反(reflexive)性、反自反(irreflexive)性、對(duì)稱(symmetric)性、反對(duì)稱(asymmetric)性、傳遞(transitive)性。1.2.1二元關(guān)系(BINARYRELATION)2023/2/425三歧性自反性、對(duì)稱性、傳遞性。等價(jià)關(guān)系(equivalencerelation)

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

1.2.2

等價(jià)類

(equivalenceclass)

2023/2/426等價(jià)類

(equivalenceclass)

S的滿足如下要求的劃分：S1、S2、S3、…、Sn…稱為S關(guān)于R的等價(jià)劃分，Si稱為等價(jià)類。⑴S=S1∪S2∪S3∪…∪Sn∪…；⑵如果i≠j，則Si∩Sj=Φ；⑶對(duì)任意的i，Si中的任意兩個(gè)元素a、b，aRb恒成立；⑷對(duì)任意的i，j，i≠j，Si中的任意元素a和Sj中的任意元素b，aRb恒不成立1.2.2指數(shù)(index)2023/2/427指數(shù)(index)

把R將S分成的等價(jià)類的個(gè)數(shù)稱為是R在S上的指數(shù)。如果R將S分成有窮多個(gè)等價(jià)類，則稱R具有有窮指數(shù)；如果R將S分成無(wú)窮多個(gè)等價(jià)類，則稱R具有無(wú)窮指數(shù)。給定集合S上的一個(gè)等價(jià)關(guān)系R，R就確定了S的一個(gè)等價(jià)分類，當(dāng)給定另一個(gè)不同的等價(jià)關(guān)系時(shí)，它會(huì)確定S的一個(gè)新的等價(jià)分類。1.2.3關(guān)系的合成(composition)2023/2/428關(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}。

1.2.3關(guān)系的合成(composition)2023/2/429⑴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∩R3R2。1.2.4遞歸定義與歸納證明2023/2/430遞歸定義(recursivedefinition)又稱為歸納定義(inductivedefinition)，可以用來(lái)定義一個(gè)集合。集合的遞歸定義由三部分組成：基礎(chǔ)(basis)：用來(lái)定義該集合的最基本的元素。歸納(induction)：指出用集合中的元素來(lái)構(gòu)造集合的新元素的規(guī)則。極小性限定：指出一個(gè)對(duì)象是所定義集合中的元素的充要條件是它可以通過(guò)有限次的使用基礎(chǔ)和歸納條款中所給的規(guī)定構(gòu)造出來(lái)。1.2.4遞歸定義與歸納證明2023/2/431歸納證明與遞歸定義相對(duì)應(yīng)。歸納證明方法包括三大步：基礎(chǔ)(basis)：證明最基本元素具有相應(yīng)性質(zhì)。歸納(induction)：證明如果某些元素具有相應(yīng)性質(zhì)，則根據(jù)這些元素用所規(guī)定的方法得到的新元素也具有相應(yīng)的性質(zhì)。根據(jù)歸納法原理，所有的元素具有相應(yīng)的性質(zhì)。

1.2.4遞歸定義與歸納證明2023/2/432定義1-17設(shè)R是S上的二元關(guān)系，我們遞歸地定義Rn的冪：⑴R0={(a，a)|a∈S}。⑵Ri=Ri-1R(i=1,2,3,4,5,…)。1.2.4遞歸定義與歸納證明2023/2/433例1-17著名的斐波那契(Fibonacci)數(shù)的定義

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

0，1，1，2，3，5，8，13，21，34，55，…1.2.4遞歸定義與歸納證明2023/2/434例1-18算術(shù)表達(dá)式⑴基礎(chǔ)：常數(shù)是算術(shù)表達(dá)式，變量是算術(shù)表達(dá)式；⑵歸納：如果E1、E2是表達(dá)式，則+E1、-E1、E1+E2、E1-E2

、E1*E2

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

1.2.4遞歸定義與歸納證明2023/2/435例1-19

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

B

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

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

1.2.4遞歸定義與歸納證明

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

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

，E1*E2的前綴形式為*E1E2，E1^E2的前綴形式為^E1E2，F(xiàn)un(E1)的前綴形式為Fun

E1。證明例1-18所定義的表達(dá)式可以用這里定義的前綴形式表示。

1.2.4遞歸定義與歸納證明2023/2/438遞歸定義給出的概念有利于歸納證明。在計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科中，有許多問(wèn)題可以用遞歸定義描述或者用歸納方法進(jìn)行證明，而且在許多時(shí)候，這樣做會(huì)帶來(lái)許多方便。

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

1.2.5關(guān)系的閉包

2023/2/439閉包(closure)

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

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

則(a，c)∈R+。(3)除(1)、(2)外，R+不再含有其他任何元素。1.2.5關(guān)系的閉包2023/2/440傳遞閉包(transitiveclosure)具有傳遞性的閉包。R+具有傳遞性?？梢宰C明，對(duì)任意二元關(guān)系R，

R+=R∪R2∪R3∪R4∪…而且當(dāng)S為有窮集時(shí)：

R+=R∪R2∪R3∪…∪R|S|1.2.5關(guān)系的閉包2023/2/441克林閉包(Kleeneclosure)R*

(1)

R0R*,RR*。

(2)

如果(a，b)，(b，c)∈R*

則(a，c)∈R*。

(3)

除(1)、(2)外，R*不再含有其他任何元素。

自反傳遞閉包(reflexiveandtransitiveclosure)

R*具有自反性、傳遞性。1.2.5關(guān)系的閉包2023/2/442可以證明，對(duì)任意二元關(guān)系R，

R*=R0∪R+R*=R0∪R∪R2∪R3∪R4∪…而且當(dāng)S為有窮集時(shí)：

R*=R0∪R∪R2∪R3∪…∪R|S|

1.2.5關(guān)系的閉包2023/2/443R1、R2是S上的兩個(gè)二元關(guān)系

(1)

Φ+=Φ。

(2)

(R1+)+=R1+。

(3)(R1*)*=R1*。

(4)R1+∪R2+(R1∪R2)+。

(5)

R1*∪R2*(R1∪R2)*。

1.3圖2023/2/444直觀地講，圖是由一些點(diǎn)和一些連接兩點(diǎn)的邊組成。含無(wú)方向的邊的圖為無(wú)向圖，含帶有方向的邊的圖為有向圖。

1.3.1無(wú)向圖2023/2/445無(wú)向圖(undirectedgraph)

設(shè)V是一個(gè)非空的有窮集合，EV×V，G=(V，E)稱為無(wú)向圖(undirectedgraph)。其中V中的元素稱為頂點(diǎn)(vertex或node)，V稱為頂點(diǎn)集，E中的元素稱為無(wú)向邊(undirectededge)，E為無(wú)向邊集。圖表示V中稱為頂點(diǎn)v的元素用標(biāo)記為v的小圈表示，E中的元素(v1，v2)用標(biāo)記為v1，v2的頂點(diǎn)之間的連線表示。

1.3.1無(wú)向圖2023/2/446路(path)如果對(duì)于0≤i≤k-1，k≥1，均有(vi，vi+1)∈E，則稱v0，v1，…，vk是G=(V，E)的一條長(zhǎng)為k的路?；芈坊蛉?cycle)當(dāng)路v0，v1，…，vk中v0=vk時(shí)，v0，v1，…，vk叫做一個(gè)回路或圈(cycle)。1.3.1無(wú)向圖2023/2/447頂點(diǎn)的度數(shù)對(duì)于v∈V，|{w|(v，w)∈E}|稱為無(wú)向圖G=(V，E)的頂點(diǎn)v的度數(shù)，記作deg(v)。對(duì)于任何一個(gè)圖，圖中所有頂點(diǎn)的度數(shù)之和為圖中邊的2倍。

2023/2/448deg(v1)=3deg(v2)=3deg(v3)=4deg(v4)=3deg(v5)=3deg(v1)+deg(v2)+deg(v3)+deg(v4)+deg(v5)=161.3.1無(wú)向圖2023/2/449連通圖如果對(duì)于v，w∈V，v≠w，v與w之間至少有一條路存在，則稱G=(V，E)是連通圖。

圖G是連通的充要條件是G中存在一條包含圖的所有頂點(diǎn)的路。

1.3.2有向圖2023/2/450有向圖(directedgraph)

G=(V，E)。V：頂點(diǎn)(vertex或node)集。(v1，v2)∈E：頂點(diǎn)v1到頂點(diǎn)v2的有向邊(directededge)，或弧(arc)，v1稱為前導(dǎo)(predecessor)，v2稱為后繼(successor)。有向路(directedpath)

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

1.3.2有向圖2023/2/451有向回路或有向圈(directedcycle)對(duì)于0≤i≤k-1，k≥1，均有(vi，vi+1)∈E，且v0=vk，則稱v0，v1，…，vk是G的一條長(zhǎng)為k的有向路為一個(gè)有向回路。有向回路又叫有向圈。

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

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

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

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

2023/2/453兩個(gè)不同的有向圖1.3.3樹2023/2/454滿足如下條件的有向圖G=(V，E)稱為一棵(有序、有向)樹(tree)：

根(root)

v：沒(méi)有前導(dǎo)，且v到樹中其他頂點(diǎn)均有一條有向路。每個(gè)非根頂點(diǎn)有且僅有一個(gè)前導(dǎo)。每個(gè)頂點(diǎn)的后繼按其拓?fù)潢P(guān)系從左到右排序。

1.3.3樹2023/2/455樹的基本概念(1)

頂點(diǎn)也可以成為結(jié)點(diǎn)。(2)

結(jié)點(diǎn)的前導(dǎo)為該結(jié)點(diǎn)的父親(父結(jié)點(diǎn)father)。(3)

結(jié)點(diǎn)的后繼為它的兒子(son)。(4)

如果樹中有一條從結(jié)點(diǎn)v1到結(jié)點(diǎn)v2的路，則稱v1是v2的祖先(ancestor),v2是v1的后代(descendant)。(5)

無(wú)兒子的頂點(diǎn)叫做葉子(leaf)。(6)

非葉結(jié)點(diǎn)叫做中間結(jié)點(diǎn)(interior)。1.3.3樹2023/2/456樹的層根處在樹的第1層(level)。

如果結(jié)點(diǎn)v處在第i層(i≥1)，則v的兒子處在第i+1層。樹的最大層號(hào)叫做該樹的高度(height)。

1.3.3樹2023/2/457二元樹如果對(duì)于v∈V，v最多只有2個(gè)兒子，則稱G=(V，E)為二元樹(binarytree)。

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

1.4語(yǔ)言2023/2/4581.4.1什么是語(yǔ)言

例如：“學(xué)大一生是個(gè)我”；“我是一個(gè)大學(xué)生”。語(yǔ)言是一定的群體用來(lái)進(jìn)行交流的工具。

必須有著一系列的生成規(guī)則、理解(語(yǔ)義)規(guī)則。1.4.1什么是語(yǔ)言2023/2/4591.4.1什么是語(yǔ)言2023/2/460斯大林：從強(qiáng)調(diào)語(yǔ)言的作用出發(fā)，把語(yǔ)言定義為“為廣大的人群所理解的字和組合這些字的方法”。

語(yǔ)言學(xué)家韋波斯特(Webster)

：為相當(dāng)大的團(tuán)體的人所懂得并使用的字和組合這些字的方法的統(tǒng)一體。

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

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

L∑*。

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

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

1.4.2形式語(yǔ)言與自動(dòng)機(jī)理論的產(chǎn)生與作用2023/2/4621951年到1956年，克林(Kleene)在研究神經(jīng)細(xì)胞中，建立了識(shí)別語(yǔ)言的系統(tǒng)——有窮狀態(tài)自動(dòng)機(jī)。

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

1.4.2形式語(yǔ)言與自動(dòng)機(jī)理論的產(chǎn)生與作用2023/2/46320世紀(jì)50年代，巴科斯范式(BackusNourForm或

BackusNormalForm，BNF)實(shí)現(xiàn)了對(duì)高級(jí)語(yǔ)言ALGOL-60的成功描述。這一成功，使得形式語(yǔ)言在20世紀(jì)60年代得到了大力的發(fā)展。尤其是上下文無(wú)關(guān)文法被作為計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的文法的最佳近似描述得到了較為深入的研究。

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

1.4.2形式語(yǔ)言與自動(dòng)機(jī)理論的產(chǎn)生與作用2023/2/464形式語(yǔ)言與自動(dòng)機(jī)理論在計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科人才的計(jì)算思維的培養(yǎng)中占有極其重要的地位。

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

1.4.2形式語(yǔ)言與自動(dòng)機(jī)理論的產(chǎn)生與作用2023/2/465計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科人才專業(yè)能力構(gòu)成

“計(jì)算思維能力”——抽象思維能力、邏輯思維能力。

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

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

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

1.4.3基本概念2023/2/468對(duì)語(yǔ)言研究的三個(gè)方面

表示(representation)——無(wú)窮語(yǔ)言的表示。

有窮描述(finitedescription)——研究的語(yǔ)言要么是有窮的，要么是可數(shù)無(wú)窮的，這里主要研究可數(shù)無(wú)窮語(yǔ)言的有窮描述。

結(jié)構(gòu)(structure)——語(yǔ)言的結(jié)構(gòu)特征。

1.4.3基本概念2023/2/469字母表(alphabet)字母表是一個(gè)非空有窮集合，字母表中的元素稱為該字母表的一個(gè)字母(letter)。又叫做符號(hào)(symbol)、或者字符(character)。非空性。有窮性。例如：

{a，b，c，d}{a，b，c，…，z}{0,1}1.4.3基本概念2023/2/470字符的兩個(gè)特性

整體性(monolith)，也叫不可分性。

可辨認(rèn)性(distinguishable)，也叫可區(qū)分性。

例（續(xù)）

{a，a′，b，b′}{aa，ab，bb}{∞，∧，∨，≥，≤}1.4.3基本概念2023/2/471字母表的乘積(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}

1.4.3基本概念2023/2/472字母表∑的n次冪

∑0={ε}

∑n=∑n-1∑

ε是由∑中的0個(gè)字符組成的。

∑的正閉包

∑+=∑∪∑2∪∑3∪∑4∪…∑的克林閉包∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪…1.4.3基本概念2023/2/473例如：{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,…}

1.4.3基本概念2023/2/474結(jié)論：∑*={x|x是∑中的若干個(gè)，包括0個(gè)字符，連接而成的一個(gè)字符串}?！?={x|x是∑中的至少一個(gè)字符連接而成的字符串}。1.4.3基本概念2023/2/475句子(sentence)∑是一個(gè)字母表，x∈∑*，x叫做∑上的一個(gè)句子。句子相等。兩個(gè)句子被稱為相等的，如果它們對(duì)應(yīng)位置上的字符都對(duì)應(yīng)相等。別稱字(word)、(字符、符號(hào))行(line)、(字符、符號(hào))串(string)。1.4.3基本概念2023/2/476出現(xiàn)(appearance)x，y∈∑*，a∈∑，句子xay中的a叫做a在該句子中的一個(gè)出現(xiàn)。當(dāng)x=ε時(shí)，a的這個(gè)出現(xiàn)為字符串xay的首字符如果a的這個(gè)出現(xiàn)是字符串xay的第n個(gè)字符，則y的首字符的這個(gè)出現(xiàn)是字符串xay的第n+1個(gè)字符。當(dāng)y=ε時(shí)，a的這個(gè)出現(xiàn)是字符串xay的尾字符例：abaabb。1.4.3基本概念2023/2/477句子的長(zhǎng)度(length)

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

例如：

|abaabb|=6|bbaa|=4|ε|=0|bbabaabbbaa|=111.4.3基本概念2023/2/478注意事項(xiàng)ε是一個(gè)句子。

{ε}≠Φ。這是因?yàn)閧ε}不是一個(gè)空集，它是含有一個(gè)空句子ε的集合。|{ε}|=1，而|Φ|=0。

1.4.3基本概念2023/2/479并置(concatenation)x，y∈∑*，x，y的并置是由串x直接相接串y所組成的。記作xy。并置又叫做連結(jié)。

串x的n次冪

x0=ε

xn=xn-1x

1.4.3基本概念2023/2/480例如：對(duì)x=001，y=1101x0=y0=εx4=001001001001y4=1101110111011101對(duì)x=0101，y=110110x2=01010101y2=110110110110x4=0101010101010101y4=1101101101101101101101101.4.3基本概念2023/2/481∑*上的并置運(yùn)算性質(zhì)⑴結(jié)合律：(xy)z=x(yz)。⑵左消去律：如果xy=xz，則y=z。⑶右消去律：如果yx=zx，則y=z。⑷

唯一分解性：存在唯一確定的a1，a2，…，an∈∑，使得x=a1a2…an。⑸單位元素：εx=xε=x。1.4.3基本概念2023/2/482前綴與后綴

設(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)。1.4.3基本概念2023/2/483公共前綴與后綴(6)y是x和w的公共前綴，如果x和w的任何公共前綴都是y的前綴，則y是x和w的最大公共前綴。(7)

如果x=zy，w=vy，則y是x和w的公共后綴(commonsuffix)。(8)y是x和w的公共后綴，如果x和w的任何公共后綴都是y的后綴，則y是x和w的最大公共后綴。1.4.3基本概念2023/2/484例字母表∑={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

1.4.3基本概念2023/2/485結(jié)論⑴x的任意前綴y有惟一的一個(gè)后綴z與之對(duì)應(yīng)，使得x=yz；反之亦然。⑶|{w|w是x的后綴}|=|{w|w是x的前綴}|。⑸{w|w是x的前綴}={w|w是x的真前綴}∪{x}，

|{w|w是x的前綴}|=|{w|w是x的真前綴}|+1。1.4.3基本概念2023/2/486結(jié)論⑹{w|w是x的后綴}={w|w是x的真后綴}∪{x}，

|{w|w是x的后綴}|=|{w|w是x的真后綴}|+1。⑺對(duì)于任意字符串w，w是自身的前綴，但不是自身的真前綴；w是自身的后綴，但不是自身的真后綴。⑻對(duì)于任意字符串w，ε是w的前綴，且是w的真前綴；ε是w的后綴，且是w的真后綴1.4.3基本概念2023/2/487約定

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

1.4.3基本概念2023/2/488子串(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的最大公共子串。

兩個(gè)串的最大公共子串并不一定是惟一的。

1.4.3基本概念2023/2/489語(yǔ)言(language)L∑*，L稱為字母表∑上的一個(gè)語(yǔ)言(language)，x∈L，x叫做L的一個(gè)句子。

例：{0，1}上的不同語(yǔ)言

{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}*1.4.3基本概念2023/2/490語(yǔ)言的乘積(product)L1∑1*，L2∑2*，語(yǔ)言L1與L2的乘積是一個(gè)語(yǔ)言，該語(yǔ)言定義為：L1L2={xy|x∈L1，y∈L2}是字母表∑1∪∑2