有限自動機(jī)理論章基礎(chǔ)知識

有限自動機(jī)理論章基礎(chǔ)知識第1頁，課件共181頁，創(chuàng)作于2023年2月聯(lián)系方式cwy樓B1-509/teacher/teacher.aspx?id=48第2頁，課件共181頁，創(chuàng)作于2023年2月課程情況學(xué)時：40（前10周）學(xué)分：２考試：閉卷、筆試大概10周考試考查：作業(yè)(3-4次)，不參加考試第3頁，課件共181頁，創(chuàng)作于2023年2月教材：

有限自動機(jī)理論

陳文宇電子科技大學(xué)出版社2007.3第4頁，課件共181頁，創(chuàng)作于2023年2月參考書形式語言與自動機(jī)理論(第2版)

蔣宗禮姜守旭清華大學(xué)出版社2007形式語言與自動機(jī)

陳有祺機(jī)械工業(yè)出版社2008第5頁，課件共181頁，創(chuàng)作于2023年2月參考書IntroductiontoAutomataTheory,Languages,andComputation(SecondEdition)

自動機(jī)理論、語言和計算導(dǎo)論

（JohnE.Hopcroft機(jī)械工業(yè)出版社）第6頁，課件共181頁，創(chuàng)作于2023年2月理論來源形式語言和自動機(jī)的理論來源于(1)Chomsky對自然語言的研究；(2)ALGOL60語言的語法描述方式；(3)Turing、Kleene、Neumann、Huffman等對自動機(jī)的研究。第7頁，課件共181頁，創(chuàng)作于2023年2月形式語言與自動機(jī)的作用

形式語言和自動機(jī)的理論已經(jīng)成為計算機(jī)科學(xué)的理論基礎(chǔ)。應(yīng)用范圍已被擴(kuò)展到生物工程、自動控制系統(tǒng)、圖像處理與模式識別等許多領(lǐng)域。第8頁，課件共181頁，創(chuàng)作于2023年2月計算機(jī)學(xué)科的專業(yè)能力

計算思維能力

算法設(shè)計與分析能力

程序設(shè)計與實現(xiàn)能力

計算機(jī)系統(tǒng)的認(rèn)知、分析、設(shè)計和運(yùn)用能力第9頁，課件共181頁，創(chuàng)作于2023年2月計算思維能力形式化描述能力抽象思維能力邏輯思維方法第10頁，課件共181頁，創(chuàng)作于2023年2月計算機(jī)學(xué)科的專業(yè)能力

相關(guān)理論是計算機(jī)學(xué)科基礎(chǔ)。理論方面的知識是計算機(jī)科學(xué)的真正靈魂。這也是計算機(jī)科學(xué)與其他學(xué)科的重要區(qū)別。第11頁，課件共181頁，創(chuàng)作于2023年2月

有限自動機(jī)理論在科學(xué)領(lǐng)域中得到直接應(yīng)用對于計算機(jī)學(xué)科人才的計算思維能力的培養(yǎng)，也具有重要作用。第12頁，課件共181頁，創(chuàng)作于2023年2月研究生階段

需要進(jìn)一步進(jìn)行抽象思維、邏輯思維、創(chuàng)造思維能力的培養(yǎng)。需要更寬厚、堅實的理論基礎(chǔ)。第13頁，課件共181頁，創(chuàng)作于2023年2月第1章基礎(chǔ)知識

本章將對有限自動機(jī)理論中所需的數(shù)學(xué)基礎(chǔ)知識作扼要的介紹。

包括集合及其運(yùn)算、關(guān)系、證明的方法、圖與樹的概念；常用術(shù)語和形式語言與自動機(jī)的發(fā)展。第14頁，課件共181頁，創(chuàng)作于2023年2月內(nèi)容：1.1集合及其運(yùn)算1.2關(guān)系1.3證明和證明的方法1.4圖與樹1.5語言1.6常用術(shù)語1.7形式語言與自動機(jī)的發(fā)展第15頁，課件共181頁，創(chuàng)作于2023年2月1.1集合及其運(yùn)算一些沒有重復(fù)的對象的全體稱為集合，而這些被包含的對象稱為該集合的元素。集合中元素可以按任意的順序進(jìn)行排列。使用大寫英文字母表示一個集合。如何刪除指定位置的元素？第16頁，課件共181頁，創(chuàng)作于2023年2月有窮集合和無窮集合

如果一個集合包含的元素個數(shù)是有限的，稱該集合為有窮集合。如果一個集合包含的元素是無限的，稱該集合為無窮集合。無窮集合又分為可數(shù)集(也稱為可列集，如正奇數(shù)集)和不可數(shù)集(如實數(shù)集)。第17頁，課件共181頁，創(chuàng)作于2023年2月集合的定義方法：列舉法命題法第18頁，課件共181頁，創(chuàng)作于2023年2月列舉法(窮舉法)對于有窮的，且元素個數(shù)較少的集合，可以采用列舉法，即將集合的所有元素全部列出，并放在一對花括號中。例如

集合A={1，2，3，4，5}第19頁，課件共181頁，創(chuàng)作于2023年2月對于某些無窮集合，也可以使用類似列舉的方法進(jìn)行描述如自然數(shù)集合：{0，1，2，3，…}第20頁，課件共181頁，創(chuàng)作于2023年2月命題法

對于集合元素較多的有窮集合或者是無窮集合，可使用集合元素的形成模式

{x|P(x)}進(jìn)行描述。其中：x表示集合中的任一元素,P(x)是一個謂詞，對x進(jìn)行限定。用來描述或判定客體性質(zhì)、特征的詞項。第21頁，課件共181頁，創(chuàng)作于2023年2月{x|P(x)}表示由滿足P(x)的一切x構(gòu)成的集合?？梢允褂米匀徽Z言，或者數(shù)學(xué)表示法來描述（表達(dá)）謂詞P(x)第22頁，課件共181頁，創(chuàng)作于2023年2月例如：{n|n是偶數(shù)}或

{n|nmod2=0}描述了由所有偶數(shù)組成的集合。第23頁，課件共181頁，創(chuàng)作于2023年2月集合的基數(shù)

若集合A包含元素x，記為x

A反之，x

A對于有窮集合A，使用|A|表示該集合包含的元素的個數(shù)，也稱基數(shù)或勢

|A|

=0

A=?

第24頁，課件共181頁，創(chuàng)作于2023年2月定義1-1子集設(shè)A,B是兩個集合，如果集合A中的每個元素都是集合B的元素，則稱集合A是集合B的子集(集合B是集合A的包集)

A

B或B

AA,B是兩個集合，如果AB，且x

B，但x

A，則稱A是B的真子集A

B第25頁，課件共181頁，創(chuàng)作于2023年2月兩個集合相等，當(dāng)且僅當(dāng)AB且BA注意：不是AB且BA第26頁，課件共181頁，創(chuàng)作于2023年2月定義1-2集合的運(yùn)算集合A與集合B的并，記為A∪B集合A的所有元素和集合B的所有元素合并在一起組成的集合。A∪B={x|x∈A或

x∈B}第27頁，課件共181頁，創(chuàng)作于2023年2月思考：什么情況下：A∪B=A

？第28頁，課件共181頁，創(chuàng)作于2023年2月集合A與集合B的交，記為A∩B是由集合A和集合B的所有公共元素組成的集合。A∩B={x|x∈A且x∈B}第29頁，課件共181頁，創(chuàng)作于2023年2月思考：什么情況下：A∩B=A

？第30頁，課件共181頁，創(chuàng)作于2023年2月集合A與集合B的差，記為AB屬于集合A但不屬于集合B的所有元素組成的集合。AB={x|x∈A且xB}第31頁，課件共181頁，創(chuàng)作于2023年2月思考:什么情況下：A-B=A

？第32頁，課件共181頁，創(chuàng)作于2023年2月如果BA，將AB稱為集合B（關(guān)于集合A）的補(bǔ)。集合A稱為集合B的全集（或論域）第33頁，課件共181頁，創(chuàng)作于2023年2月定義1-3冪集設(shè)A為一個集合，那么A的冪集為A的所有子集組成的集合記為2A2A={B|B

A}第34頁，課件共181頁，創(chuàng)作于2023年2月例1-1

集合A={1，2，3}，則A的冪集為:2A={?，{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，

{1，2，3}}任取其中2個元素構(gòu)成的集合第35頁，課件共181頁，創(chuàng)作于2023年2月冪集2A的元素個數(shù)當(dāng)集合A為有窮集時，如果|A|=n，那么A的冪集2A的元素個數(shù)(集合A的所有子集的個數(shù))為2n。（集合A的冪集表示為2A的原因）無論集合A是有窮集合，還是無窮集合，都使用2A表示集合A的冪集。第36頁，課件共181頁，創(chuàng)作于2023年2月定義1-4笛卡兒積集合A和B的笛卡兒乘積A

B（也簡記為AB）A

B={(a,b)|a

A且bB}當(dāng)集合A、B為有窮集時|A

B|=|A|*|

B|第37頁，課件共181頁，創(chuàng)作于2023年2月例1-2設(shè)A={a,b,c},B={0,1},則A

B={(a,0),(a,1),(b,0),(b,1),(c,0),(c,1)}B

A={(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)}也可根據(jù)約定記為：A

B={a0,a1,b0,b1,c0,c1}第38頁，課件共181頁，創(chuàng)作于2023年2月思考什么情況下：A

B=B

A

?第39頁，課件共181頁，創(chuàng)作于2023年2月練習(xí)1～10之間的和為10的整數(shù)集合的集合

第40頁，課件共181頁，創(chuàng)作于2023年2月

{{1,9},{2,8},{3,7},{4,6},

{1,2,7},{1,3,6},{1,4,5},

{2,3,5},{1,2,3,4}}注意：沒有{5，5}第41頁，課件共181頁，創(chuàng)作于2023年2月1.2關(guān)系1.2.1二元關(guān)系1.2.2等價關(guān)系與等價類1.2.3關(guān)系的合成第42頁，課件共181頁，創(chuàng)作于2023年2月1.2.1二元關(guān)系設(shè)A和B為兩個集合，則A

B的任何一個子集稱為A到B的一個二元關(guān)系。若R為A到B的關(guān)系，當(dāng)

(a,b)

R時，可記為aRb若A

=

B，則稱R為A上的關(guān)系第43頁，課件共181頁，創(chuàng)作于2023年2月思考：如果集合A和B都是有窮集合，則

A到B的二元關(guān)系有多少個？

A到B的一個二元關(guān)系

最多可以有多少個元素？

最少可以有多少個元素第44頁，課件共181頁，創(chuàng)作于2023年2月例1-3設(shè)A為正整數(shù)集合，則A上的關(guān)系“<”是集合{(a,b)|a,b

A,且a<b}={(1,2),(1,3),(1,4),...(2,3),(2,4),(2,5),......}第45頁，課件共181頁，創(chuàng)作于2023年2月1.2.2等價關(guān)系設(shè)R是A上的二元關(guān)系(1)如果對于a

A，都有

(a,a)

R則稱R是自反的。第46頁，課件共181頁，創(chuàng)作于2023年2月(2)如果對于a,b

A

(a,b)

R

(b,a)

R則稱R是對稱的。第47頁，課件共181頁，創(chuàng)作于2023年2月(3)若對a,b,c

A(a,b)R且(b,c)

R(a,c)

R

則稱R為傳遞的。第48頁，課件共181頁，創(chuàng)作于2023年2月定義1-6如果集合A上的二元關(guān)系R是自反的、對稱的和傳遞的則稱R為等價關(guān)系。第49頁，課件共181頁，創(chuàng)作于2023年2月等價關(guān)系的性質(zhì)等價關(guān)系的一個重要性質(zhì)為：集合A上的一個等價關(guān)系R可以將集合A劃分為若干個互不相交的子集--等價類第50頁，課件共181頁，創(chuàng)作于2023年2月對A中的每個元素a，使用[a]表示a的等價類，即[a]={b|aRb}。等價關(guān)系R將集合A劃分成的等價類的數(shù)目----等價關(guān)系的指數(shù)。第51頁，課件共181頁，創(chuàng)作于2023年2月例1-3自然數(shù)集合N上的模3同余關(guān)系

R={(a,b)|a,b

N,且amod3=bmod3}是一個等價關(guān)系。第52頁，課件共181頁，創(chuàng)作于2023年2月{0,3,6,…,3n,…}第1個等價類；{1,4,7,…,3n+1,…}第2個等價類；{2,5,8,…,3n+2,…}第3個等價類；分別記為[0]，[1]和[2]。第53頁，課件共181頁，創(chuàng)作于2023年2月

N=[0]∪[1]∪[2]等價關(guān)系的指數(shù)為3第54頁，課件共181頁，創(chuàng)作于2023年2月思考自然數(shù)集合N上的相等關(guān)系第55頁，課件共181頁，創(chuàng)作于2023年2月1.2.3關(guān)系的合成關(guān)系可以進(jìn)行合成。第56頁，課件共181頁，創(chuàng)作于2023年2月定義1-7設(shè)R1

A

B是A到B的(二元)關(guān)系

R2

B

C是B到C

的(二元)關(guān)系R1與R2的合成是A到C的(二元)關(guān)系R1οR2=

{(a,c)|(a,b)

R1且(b,c)

R2}第57頁，課件共181頁，創(chuàng)作于2023年2月例1-5R1和R2的是集合{1,2,3,4}上的關(guān)系R1={(1,1),(1,2),(2,3),(3,4)}R2={(2,4),(4,1),(4,3),(3,1),(3,4)}則R1οR2

={(1,4),(2,1),(2,4),(3,1),(3,3)}

R2οR1

={(4,1),(4,2),(4,4),(3,1),(3,2)}有？個關(guān)系第58頁，課件共181頁，創(chuàng)作于2023年2月定義1-8關(guān)系的n次冪設(shè)R是S上的二元關(guān)系，則Rn遞歸定義為：(1)R0={(a,a)|a

S}(2)Ri=Ri-1ο

R

(i=1,2,3,…)第59頁，課件共181頁，創(chuàng)作于2023年2月定義1-9關(guān)系的閉包設(shè)R是S上的二元關(guān)系，R的正閉包R+為(1)

R

R+

；(2)若(a,

b),

(b,c)

R+,則(a,c)

R+；(3)除(1)，(2)外，R+不再含有其他任何元素。第60頁，課件共181頁，創(chuàng)作于2023年2月

普通定義:R+R+=R

∪

R2

∪

R3

∪…第61頁，課件共181頁，創(chuàng)作于2023年2月且當(dāng)S為有窮集時，有R+=R

∪R2

∪

R3

∪…∪

R|s|第62頁，課件共181頁，創(chuàng)作于2023年2月關(guān)系的克林閉包R*

=R0

∪

R+第63頁，課件共181頁，創(chuàng)作于2023年2月例1-6設(shè)R1={(a,b),(c,d),(b,d),(b,b),(d,e)}R2={(a,a),(b,c),(d,c),(e,d),(c,a)}則R1ο

R2={(a,c),(c,c),(b,c),(d,d)}第64頁，課件共181頁，創(chuàng)作于2023年2月R1+={(a,b),(c,d),(b,d),(b,b),(d,e),(a,d),(a,e),(c,e),(b,e)}R1*=

{(a,a),(b,b),(c,c),(d,d),(e,e)}

∪

R1+

第65頁，課件共181頁，創(chuàng)作于2023年2月1.3證明和證明的方法

形式語言和有限自動機(jī)有很強(qiáng)的理論性，許多的論斷以定理的形式進(jìn)行描述，而定理的正確性是需要進(jìn)行證明的。形式語言和有限自動機(jī)理論中定理的證明普遍使用反證法和歸納法第66頁，課件共181頁，創(chuàng)作于2023年2月1.3.1反證法1.3.2歸納法1.3.3遞歸定義與歸納證明第67頁，課件共181頁，創(chuàng)作于2023年2月1.3.1反證法(歸謬法)

利用反證法證明一個命題時，一般的步驟為：(1)假設(shè)該命題不成立；(2)進(jìn)行一系列的推理；(3)在推理的過程中如果出現(xiàn)了下列情況之一：第68頁，課件共181頁，創(chuàng)作于2023年2月與已知條件矛盾；與公理矛盾；與已證過的定理矛盾；與臨時的假定矛盾；自相矛盾；反證法(續(xù))第69頁，課件共181頁，創(chuàng)作于2023年2月

由于上述矛盾的出現(xiàn)，可以斷言“假設(shè)該命題不成立”的假設(shè)不正確；從而肯定原命題正確。反證法(續(xù))第70頁，課件共181頁，創(chuàng)作于2023年2月反證法例子

是無理數(shù)。第71頁，課件共181頁，創(chuàng)作于2023年2月演繹與歸納演繹是從普遍性的理論知識出發(fā)，去認(rèn)識個別的、特殊的現(xiàn)象的一種邏輯推理方法。演繹的基本形式是三段論。歸納是根據(jù)個別的、特殊的現(xiàn)象，得到普遍性知識的邏輯推理方法。第72頁，課件共181頁，創(chuàng)作于2023年2月1.3.2歸納法

歸納法是從特殊到一般的邏輯推理方法。分為完全歸納法和不完全歸納法兩種形式。第73頁，課件共181頁，創(chuàng)作于2023年2月

完全歸納法是根據(jù)一切情況的分析而作出的推理。由于必須考慮所有的情況，得出的結(jié)論是完全可靠的。第74頁，課件共181頁，創(chuàng)作于2023年2月歸納法（續(xù)）不完全歸納法是根據(jù)一部分情況作出的推理。不能作為嚴(yán)格的證明方法。第75頁，課件共181頁，創(chuàng)作于2023年2月

在自動機(jī)理論中，普遍使用數(shù)學(xué)歸納法證明某個命題。第76頁，課件共181頁，創(chuàng)作于2023年2月

數(shù)學(xué)歸納法可以使用“有限步驟”解決“無限”問題。第77頁，課件共181頁，創(chuàng)作于2023年2月數(shù)學(xué)歸納法對于一切非負(fù)整數(shù)n的命題M(n)(1)M(0)為真；(2)假設(shè)對于任意的k

0，M(k)為真，能夠證明M(k+1)為真(3)則對一切n

0，M(n)為真。第78頁，課件共181頁，創(chuàng)作于2023年2月第(1)步稱為歸納基礎(chǔ)第(2)步稱為歸納步驟第(2)步中“設(shè)對于任意的k

0，M(k)為真”，稱為歸納假設(shè)第79頁，課件共181頁，創(chuàng)作于2023年2月數(shù)學(xué)歸納法的簡化對于0，證明結(jié)論成立；假設(shè)結(jié)論對于n成立，證明結(jié)論對于n＋１成立。第80頁，課件共181頁，創(chuàng)作于2023年2月1.3.3集合遞歸定義與歸納證明遞歸定義

(1)基礎(chǔ)

(2)歸納

(3)極小性限定(有限性)第81頁，課件共181頁，創(chuàng)作于2023年2月遞歸定義集合步驟(1)基礎(chǔ)：首先定義該集合中最基本的元素

x1,x2,x3,…xm

第82頁，課件共181頁，創(chuàng)作于2023年2月(2)歸納：對于該集合中的元素x1,x2,x3,…xn使用某種組合方法對這些元素進(jìn)行處理后所得的新元素在該集合中第83頁，課件共181頁，創(chuàng)作于2023年2月(3)有限性：只有滿足(1)和(2)的元素才在集合中第84頁，課件共181頁，創(chuàng)作于2023年2月遞歸定義集合的優(yōu)點(diǎn)除集合的基本元素(直接定義)外集合中的元素的產(chǎn)生遵從相同的規(guī)律。第85頁，課件共181頁，創(chuàng)作于2023年2月例1-6Fibonacci數(shù)Fibonacci數(shù)組成的集合為：{0,1,1,2,3,5,8,13,21,34,55,…}第86頁，課件共181頁，創(chuàng)作于2023年2月(1)基礎(chǔ)：

0和1是最基本的兩個元素；(2)歸納：若m是第i個元素,n是第i+1個元素則第i+2個元素為n+m;(3)只有滿足(1)和(2)的數(shù)，才是集合的元素第87頁，課件共181頁，創(chuàng)作于2023年2月例括號匹配的串構(gòu)成的集合的定義{(),()(),(()),…}（1）基礎(chǔ)：

()是最基本的串

第88頁，課件共181頁，創(chuàng)作于2023年2月（2）歸納：若S是括號匹配的串,則(S)是括號匹配的串若S是括號匹配的串,則SS是括號匹配的串第89頁，課件共181頁，創(chuàng)作于2023年2月練習(xí)給出下列計算的遞歸定義字符串的倒序第90頁，課件共181頁，創(chuàng)作于2023年2月1.4圖與樹1.3.1無向圖1.3.2有向圖1.3.3樹第91頁，課件共181頁，創(chuàng)作于2023年2月圖

現(xiàn)實世界中，許多問題可以抽象成圖來表示。直觀地，圖是由一些點(diǎn)和連接兩點(diǎn)的邊組成的。第92頁，課件共181頁，創(chuàng)作于2023年2月定義1-10無向圖設(shè)V是一個非空的有窮集合E

V

V稱G=(V,E)為一個無向圖。其中，V稱為頂點(diǎn)集E稱為無向邊集第93頁，課件共181頁，創(chuàng)作于2023年2月無向圖中的邊都沒有方向(vi,vj)和(vj,vi)表示的是同一條邊第94頁，課件共181頁，創(chuàng)作于2023年2月無向圖頂點(diǎn)的度:該頂點(diǎn)相關(guān)聯(lián)的邊的條數(shù)記為deg(v)，其中：vV第95頁，課件共181頁，創(chuàng)作于2023年2月練習(xí)設(shè)G=(V，E)為一個無向圖，則第96頁，課件共181頁，創(chuàng)作于2023年2月數(shù)學(xué)歸納法證明：(1)基礎(chǔ)。當(dāng)圖|E|=0時，圖中各結(jié)點(diǎn)的度均為0，因此第97頁，課件共181頁，創(chuàng)作于2023年2月(2)歸納。假設(shè)|E|=n時結(jié)論成立

|E|=n+1時，圖添加一條邊令為(vi,vj)。第98頁，課件共181頁，創(chuàng)作于2023年2月則deg(vi)，deg(vj)都增加1而其它結(jié)點(diǎn)的度保持不變因此在新圖中仍有第99頁，課件共181頁，創(chuàng)作于2023年2月(3)由歸納法原理結(jié)論對任意無向圖成立。第100頁，課件共181頁，創(chuàng)作于2023年2月例V={v1,v2,v3,v4,v5}E={(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),(v4,v5)}deg(v1)=deg(v2)=deg(v4)=deg(v5)=3deg(v3)=4v1v2v3v4v5第101頁，課件共181頁，創(chuàng)作于2023年2月有向圖(vi,vj)表示的是從前導(dǎo)vi出發(fā)，到達(dá)后繼vj的一條邊。(vi,vj)和(vj,vi)表示的是不同邊有向圖頂點(diǎn)的度：

入度與出度第102頁，課件共181頁，創(chuàng)作于2023年2月例G2V={v1,v2,v3,v4,v5}E={(v1,v2),(v1,v3),(v2,v3),(v3,v4),(v3,v5),(v4,v1),(v4,v5),(v5,v2),(v5,v4)}

ideg(v1)=1,odeg(v1)=2ideg(v2)=2,odeg(v2)=1v1v2v3v4v5第103頁，課件共181頁，創(chuàng)作于2023年2月定義1-12有向路設(shè)G=(V，E)為一個有向圖如果對于0

i

k–1，均有(vi,vi+1)

E稱v0，v1，…，vk是一條(有向)路第104頁，課件共181頁，創(chuàng)作于2023年2月有向回路當(dāng)v0=vk時稱為一條(有向)回路。第105頁，課件共181頁，創(chuàng)作于2023年2月思考從v1到v4有多少條路？v1v2v3v4v5第106頁，課件共181頁，創(chuàng)作于2023年2月定義1-13樹設(shè)G=(V,E)為一個有向圖。當(dāng)G滿足如下條件時，稱G為一棵(有向)樹：第107頁，課件共181頁，創(chuàng)作于2023年2月1)vV，v沒有前導(dǎo)，且v到樹中的其他頂點(diǎn)都有一條有向路，該頂點(diǎn)稱為樹G的根；2)每個非根頂點(diǎn)有且僅有一個前導(dǎo)；3)每個頂點(diǎn)的后繼按其拓?fù)潢P(guān)系從左到右排序。第108頁，課件共181頁，創(chuàng)作于2023年2月1.5語言任意字符的集合是一個字母表。如26個英文字母表；10個阿拉伯?dāng)?shù)字字母表；24個希臘字母表；二進(jìn)制字母表第109頁，課件共181頁，創(chuàng)作于2023年2月字母表有非空性、有窮性、單一性一般使用∑表示字母表。第110頁，課件共181頁，創(chuàng)作于2023年2月字符串

字母表中的字母按照某種順序排列成的字符的序列第111頁，課件共181頁，創(chuàng)作于2023年2月語言字符串的集合第112頁，課件共181頁，創(chuàng)作于2023年2月語言研究的三個方面1）如何給出一個語言的表示。對于有窮語言，使用列舉法；對于無窮語言，需要考慮語言的有窮描述。第113頁，課件共181頁，創(chuàng)作于2023年2月語言研究的三個方面（續(xù)）2）對于一個給定的無窮語言是否存在有窮描述（有窮表示）。注意：并不是所有的無窮語言都存在有窮表示。第114頁，課件共181頁，創(chuàng)作于2023年2月語言研究的三個方面（續(xù)）3）具有有窮表示的語言的結(jié)構(gòu)以及結(jié)構(gòu)的描述問題。第115頁，課件共181頁，創(chuàng)作于2023年2月1.6常用術(shù)語(1)用代表空串，{}代表僅含有空串的集合。(2)用代表空集，表示一個元素都不包含的集合。(3)用代表字母表。第116頁，課件共181頁，創(chuàng)作于2023年2月常用術(shù)語（續(xù)）(4)用代表兩個字符串與的連接（并置）若=a1a2a3…an,=b1b2b3…bm;則=a1a2a3…anb1b2b3…bm。特別：=

=第117頁，課件共181頁，創(chuàng)作于2023年2月用代表n的n次連接0=n=n-1，n>0第118頁，課件共181頁，創(chuàng)作于2023年2月(5)用AB代表集合A與B的連接A={a1,a2,a3,…,an}B={b1,b2,b3,…,bm}第119頁，課件共181頁，創(chuàng)作于2023年2月AB={a1b1，a1b2，a1b3，…，a1bm，a2b1，a2b2，a2b3，…，a2bm，a3b1，a3b2，a3b3，…，a3bm，…anb1，anb2，anb3，…，anbm}第120頁，課件共181頁，創(chuàng)作于2023年2月注意：

AФ=ФA=Ф第121頁，課件共181頁，創(chuàng)作于2023年2月一般，AB與BA是不相等的。第122頁，課件共181頁，創(chuàng)作于2023年2月思考:AB與BA在什么情況下相等?1)當(dāng)A=B；2)A或B中有一個為{ε},則

A{ε}={ε}A=A3)A和B中有一個為Ф，則

AФ=ФA=Ф第123頁，課件共181頁，創(chuàng)作于2023年2月6)An代表集合A的n次連接(冪)A的n次冪定義為：(1)A0={}(2)An=An-1An1第124頁，課件共181頁，創(chuàng)作于2023年2月7)

A*代表A上所有字符串的集合即表示集合A中的所有字符串進(jìn)行任意次連接而形成的串的集合第125頁，課件共181頁，創(chuàng)作于2023年2月A*稱為集合A的閉包(克林閉包)A*=A0∪A1∪A2∪…∪An第126頁，課件共181頁，創(chuàng)作于2023年2月例

A={0，1}A0={ε}即長度為0的0和1組成的串的集合A1=A={0,1}即長度為1的0和1組成的串的集合第127頁，課件共181頁，創(chuàng)作于2023年2月A2=AA={00,01,10,11}

即長度為2的0和1組成的串集合

A3=A2A={000,001,010,011,100,101,110,111}

即長度為3的0和1組成的串的集合第128頁，課件共181頁，創(chuàng)作于2023年2月…

A*=A0∪A1∪A2∪…∪An={0和1組成的所有的串}={w|w是0和1組成的串}第129頁，課件共181頁，創(chuàng)作于2023年2月如果串ω是集合A的閉包中的串，也稱ω是集合A上的串。對于任何集合A有(A*)*=A*第130頁，課件共181頁，創(chuàng)作于2023年2月8)

A+稱為A的正閉包A+=A∪A2∪A3∪…∪An第131頁，課件共181頁，創(chuàng)作于2023年2月A*

與A+A*=A+∪

A0即A*=A+∪

{ε}第132頁，課件共181頁，創(chuàng)作于2023年2月注意：A0={ε}

{ε}*={ε}

{ε}+={ε}Ф*={ε}

Ф+=Ф第133頁，課件共181頁，創(chuàng)作于2023年2月思考是否對于任意的集合A，都有

A+=A*-{ε}第134頁，課件共181頁，創(chuàng)作于2023年2月辨析與思考{}與?|{}|=1|?|=0{}×A=A?

×A=?第135頁，課件共181頁，創(chuàng)作于2023年2月9）給定字母表∑，則∑*的任意子集L稱為字母表∑上的一個語言。本質(zhì)上，語言L是字母表∑上的字符串形成的集合。第136頁，課件共181頁，創(chuàng)作于2023年2月10)給定字母表∑，L是字母表∑上的一個語言，ω是L的一個字符串稱ω為L的一個句子。第137頁，課件共181頁，創(chuàng)作于2023年2月串的長度|ε|=0；|ω|=n；若ω=a1a2a3…an；其中：ai∈，n>0；第138頁，課件共181頁，創(chuàng)作于2023年2月11)前綴和后綴：x,y,z∈∑*，且x=yzy是x的前綴；如果zε，則稱y是x的真前綴；z是x的后綴；如果yε，則稱z是x的真后綴；第139頁，課件共181頁，創(chuàng)作于2023年2月例1-13串a(chǎn)bcde：前綴：ε，a，ab，abc，abcd，abcde真前綴：ε，a，ab，abc，abcd后綴：ε，e，de，cde，bcde，abcde真后綴：ε，e，de，cde，bcde第140頁，課件共181頁，創(chuàng)作于2023年2月對于任意字符串x，x的前綴有|x|+1個

真前綴有|x|個第141頁，課件共181頁，創(chuàng)作于2023年2月對于任何字符串x，x的任意前綴y有惟一的一個后綴z與之對應(yīng)，使得x=yz，反之亦然；對于任何字符串x，x的任意真前綴y有惟一的一個真后綴z與之對應(yīng)，使得x=yz，反之亦然（除了ε以外）；第142頁，課件共181頁，創(chuàng)作于2023年2月對于任何字符串xx是自身的前綴，但不是真前綴x是自身的后綴，但不是真后綴第143頁，課件共181頁，創(chuàng)作于2023年2月對于任何字符串xε，ε是x的前綴，且是真前綴；ε是x的后綴，且是真后綴；第144頁，課件共181頁，創(chuàng)作于2023年2月思考：對于ε，前綴是？真前綴？后綴是？真后綴？第145頁，課件共181頁，創(chuàng)作于2023年2月12)語言的前綴性質(zhì)設(shè)L是某個字母表上的語言如果L中的任何句子都是另一個句子的真前綴，則稱語言L具有前綴性質(zhì)。第146頁，課件共181頁，創(chuàng)作于2023年2月例1-14字母表{0，1}上的語言L1={0n|n>=0}具有前綴性質(zhì)；語言L2={0n1|n>=0}不具有前綴性質(zhì)。第147頁，課件共181頁，創(chuàng)作于2023年2月語言與句子設(shè)是一個字母表，L

*,L稱為字母表上的一個語言x

L,x稱為L的一個句子。語言的可分為有窮語言與無窮語言第148頁，課件共181頁，創(chuàng)作于2023年2月語言的乘積設(shè)1,2是兩個字母表L1

1*,L2

2*,語言L1與L2的乘積是一個語言：L1L2={xy|xL1,yL2}該語言是字母表1∪2上的語言第149頁，課件共181頁，創(chuàng)作于2023年2月語言的例子字母表

{0,1}上的一些語言：{00,11}{0,1,00,11}{0}{0,1}*{1}{0,1}*{111}{0,1}*第150頁，課件共181頁，創(chuàng)作于2023年2月語言的n次冪設(shè)是一個字母表，L

*,L的n次冪是一個語言(1)當(dāng)n=0時，Ln

={}(2)當(dāng)n1時，Ln

=Ln-1

L第151頁，課件共181頁，創(chuàng)作于2023年2月語言的例子令

={0,1}，

L={0,1}

L={0,1,00,01,10,11,…}=+

L={,0,1,00,01,10,11,…}=*第152頁，課件共181頁，創(chuàng)作于2023年2月L={0n1n|n1}L={0n1m0k|n,m,k1}L={0n1m0k|n,m,k０}第153頁，課件共181頁，創(chuàng)作于2023年2月語言的閉包L的正閉包L+是一個語言：L+=L

∪

L2∪

L3∪…L的克林閉包L*是一個語言：L*=L0∪

L+第154頁，課件共181頁，創(chuàng)作于2023年2月1.7形式語言與自動機(jī)的發(fā)展語言學(xué)家Chomsky(喬姆斯基)最早從產(chǎn)生語言的角度研究語言。1956年，通過抽象，Chomsky將語言形式地定義為由一個字母表的字母組成的一些串的集合：對于任意語言L，有一個字母表，使得LC∑*?？梢栽谧帜副砩习凑找欢ǖ男纬梢?guī)則定義一個文法，該文法產(chǎn)生的所有的句子組成的集合就是該文法產(chǎn)生的語言。第155頁，課件共181頁，創(chuàng)作于2023年2月1959年，Chomsky根據(jù)產(chǎn)生語言的文法的產(chǎn)生式的不同特點(diǎn)，將文法和對應(yīng)產(chǎn)生的語言分為三大類。第156頁，課件共181頁，創(chuàng)作于2023年2月數(shù)學(xué)家Kleene（克林）在1951~1956年間，從識別語言的角度來研究語言，給出了語言的另一種描述方式。Kleene在研究神經(jīng)細(xì)胞時建立了自動機(jī)模型，Kleene使用該模型來識別（接收）一個語言：按照某種識別規(guī)則構(gòu)造自動機(jī)，該自動機(jī)就定義了一個語言，該語言由自動機(jī)能夠識別的所有字符串構(gòu)成。第157頁，課件共181頁，創(chuàng)作于2023年2月語言的兩種不同的定義方式進(jìn)一步引起了人們的研究興趣。一個語言，可以采取不同的描述方式：文法產(chǎn)生語言和自動機(jī)識別語言。由于是同一個語言，兩種方式應(yīng)該是等價的，也就存在兩種方式之間的等價的相互轉(zhuǎn)換方法。第158頁，課件共181頁，創(chuàng)作于2023年2月Chomsky于1959年，將他本人的形式語言的研究成果和Kleene的自動機(jī)的研究成果結(jié)合起來，不僅確定了文法和自動機(jī)分別從產(chǎn)生和識別角度定義語言，而且證明了文法與自動機(jī)的等價性。此時，形式語言與自動機(jī)理論才真正誕生。并被置于數(shù)學(xué)的光芒之下。第159頁，課件共181頁，創(chuàng)作于2023年2月形式語言與自動機(jī)理論出現(xiàn)后，迅速在計算機(jī)科學(xué)技術(shù)領(lǐng)域得到了應(yīng)用。使用巴科斯-諾爾范式（BNF--Backus-NaurForm）成功地對高級程序設(shè)計語言ALGOL-60的詞法和語法規(guī)則進(jìn)行了形式化的描述（實際上，巴科斯-諾爾范式就是上下文無關(guān)文法的產(chǎn)生式另一種表示方式）。這一成功，使得形式語言與自動機(jī)理論得到了進(jìn)一步的發(fā)展。第160頁，課件共181頁，創(chuàng)作于2023年2月尤其是上下文無關(guān)文法，被作為計算機(jī)程序設(shè)計語言語法的最佳近似描述得到了較為深入的研究。后來，人們又將上下文無關(guān)文法應(yīng)用到了模式匹配和模型化處理等方面，而這些內(nèi)容都是算法描述和分析、計算復(fù)雜性理論和可計算性理論的研究基礎(chǔ)。第161頁，課件共181頁，創(chuàng)作于2023年2月形式語言理論的研究對象與以前的所有語言研究不同，不止自然語言，而是人類一切語言：既有自然語言，也有人工語言，包括計算機(jī)編程的高級語言。喬姆斯基的形式語言理論得到了多重驗證，于是才為語言學(xué)界和計算機(jī)科學(xué)界所折服，“引發(fā)了語言學(xué)中伽利略式的科學(xué)革命的開端?！钡?62頁，課件共181頁，創(chuàng)作于2023年2月喬姆斯基的形式語言理論得到過計算機(jī)科學(xué)的三種驗證。第163頁，課件共181頁，創(chuàng)作于2023年2月驗證一：喬氏4型文法與4種語言自動機(jī)一一對應(yīng)。第164頁，課件共181頁，創(chuàng)作于2023年2月驗證二：計算機(jī)所使用的各種高級語言，如ALGOL、FORTRAN、PASCAL、C、LISP等，都遵循一種程序語言文法描述的范式，即巴科斯—諾爾范式。計算機(jī)科學(xué)家發(fā)現(xiàn)，巴科斯—諾爾范式等價于喬姆斯基的2型文法，即與上下文無關(guān)文法。而喬姆斯基的3型文法——正則文法