形式語言與自動化理論第一章緒論20160919

1、2022-3-121計算機軟件理論基礎(chǔ)計算機軟件理論基礎(chǔ)課程目的和基本要求課程目的和基本要求2022-3-122課程性質(zhì)課程性質(zhì)技術(shù)基礎(chǔ)技術(shù)基礎(chǔ) 基礎(chǔ)知識要求基礎(chǔ)知識要求 數(shù)學(xué)分析數(shù)學(xué)分析（或者高等數(shù)學(xué)），（或者高等數(shù)學(xué)），離散數(shù)學(xué)離散數(shù)學(xué) 主要特點主要特點 抽象和形式化抽象和形式化 理論證明和構(gòu)造性理論證明和構(gòu)造性 基本模型的建立與性質(zhì)基本模型的建立與性質(zhì) 課程目的和基本要求課程目的和基本要求2022-3-123本專業(yè)人員本專業(yè)人員4 4種基本的專業(yè)能力種基本的專業(yè)能力計算思維能力計算思維能力算法的設(shè)計與分析能力算法的設(shè)計與分析能力程序設(shè)計和實現(xiàn)能力程序設(shè)計和實現(xiàn)能力計算機軟硬件系統(tǒng)的認知、

2、分析、設(shè)計與應(yīng)用能力計算機軟硬件系統(tǒng)的認知、分析、設(shè)計與應(yīng)用能力計算思維能力計算思維能力邏輯思維能力和抽象思維能力邏輯思維能力和抽象思維能力構(gòu)造模型對問題進行形式化描述構(gòu)造模型對問題進行形式化描述理解和處理形式模型理解和處理形式模型課程目的和基本要求課程目的和基本要求 2022-3-124知識知識掌握掌握正則語言正則語言、上下上下文無關(guān)語言的文法文無關(guān)語言的文法、識別模型及識別模型及其基本性質(zhì)其基本性質(zhì)、圖靈機的基本知識圖靈機的基本知識。能力能力培養(yǎng)學(xué)生的形式化描述和抽象思維能力。培養(yǎng)學(xué)生的形式化描述和抽象思維能力。使學(xué)生了解和初步掌握使學(xué)生了解和初步掌握“問題、形式化描述、自動化問題、形式化

3、描述、自動化（計算機化）（計算機化）”這一最典型的計算機問題求解思路。這一最典型的計算機問題求解思路。 主要內(nèi)容主要內(nèi)容 2022-3-125語言的語言的文法文法描述。描述。RLRLRGRG、 FAFA、RERE、RLRL的性質(zhì)的性質(zhì) 。CFLCFLCFG(CNFCFG(CNF、GNF)GNF)、PDAPDA、CFLCFL的性質(zhì)。的性質(zhì)。 TMTM基本基本TMTM、構(gòu)造技術(shù)、構(gòu)造技術(shù)、TMTM的修改。的修改。CSLCSLCSGCSG、LBALBA。教材及主要參考書目教材及主要參考書目2022-3-126蔣宗禮，姜守旭蔣宗禮，姜守旭. 形式語言與自動機理論形式語言與自動機理論. 北京：北京：清華

4、大學(xué)出版社，清華大學(xué)出版社，2013年年 (第第3版）版）John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation (2nd Edition). Addison-Wesley Publishing Company, 2001 John E Hopcroft, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-W

5、esley Publishing Company, 1979成績評定2022-3-1271. 平時考勤、作業(yè)-40%2. 期末考試-60%第第1章章 緒論緒論2022-3-1281.1 集合的基礎(chǔ)知識集合的基礎(chǔ)知識 1.1.1 集合及其表示集合及其表示集合：集合：一定范圍內(nèi)的一定范圍內(nèi)的、確定的確定的、并且、并且彼此可以區(qū)分的對彼此可以區(qū)分的對象象匯集在一起形成的整體叫做匯集在一起形成的整體叫做集合集合(set)， ，簡簡稱稱為為集集(set)。 。 元素：集合的成元素：集合的成員為該員為該集合的集合的元素元素(element)。 。 集合描述形式。集合描述形式。 基數(shù)?；鶖?shù)。 集合的分集合的

6、分類類。 。 1.1.2 1.1.2 集合之間的關(guān)系集合之間的關(guān)系 2022-3-129子集子集 如果如果集合集合A中的每個元素都是集合中的每個元素都是集合B的元素的元素，則稱，則稱集合集合A是集合是集合B的的子集子集(subset)，集合，集合B是集合是集合A的的包集包集(container)。記作。記作A B。也可記作。也可記作B A。A B讀作集合讀作集合A包含在集合包含在集合B中；中；B A讀作集合讀作集合B包含集合包含集合A。如果如果A B，且，且 xB，但，但x A，則稱，則稱A是是B的的真子真子集集(proper subset)，記作，記作A B 1.1.2 1.1.2 集合之間

7、的關(guān)系集合之間的關(guān)系2022-3-1210集合相等集合相等 如果集合如果集合A，B含有的元素完全相同，則稱集合含有的元素完全相同，則稱集合A與集合與集合B相等相等(equivalence)，記作，記作A=B。對任意集合對任意集合A、B、C： A=B iff A B且且B A。 如果如果A B，則，則|A|B|。 如果如果A B，則，則|A|B|。 如果如果A是是有窮集有窮集，且，且A B，則，則|B|A|。1.1.2 1.1.2 集合之間的關(guān)系集合之間的關(guān)系2022-3-1211 如果如果A B，則對，則對 xA，有，有xB。如果如果A B，則對，則對 xA，有，有xB并且并且 xB，但，但x

8、 A。 如果如果A B且且B C，則，則A C。 如果如果A B且且B C，或者，或者A B且且B C，或者，或者A B且且B C，則，則A C。 如果如果A=B，則，則|A|=|B|。1.1.3 1.1.3 集合的運算集合的運算 2022-3-1212并并(union) A與與B的的并并(union)是一個集合，該集合中的元素要么是一個集合，該集合中的元素要么是是A的元素，要么是的元素，要么是B的元素，記作的元素，記作AB。 AB=a|aA或者或者aB A1A2An=a| i，1in，使得，使得aAi A1A2An =a| i，iN,使得使得aAi1iiA,|AaSAaASA交交(inter

9、section) 2022-3-1213集合集合A和和B中中都有的都有的所有元素放在一起構(gòu)成的集合所有元素放在一起構(gòu)成的集合為為A與與B的的交交 ，記作，記作AB。 AB=a|aA且且aB “”為交運算符，為交運算符，AB讀作讀作A交交B。 如果如果AB=，則稱，則稱A與與B不相交。不相交。 AB= BA。 (AB)C=A(BC)。 AA=A。交交(INTERSECTION)2022-3-1214 AB=A iff A B。 A=。 |AB|min|A|，|B|。 A(BC)=(AB)(AC)。 A(BC)=(AB)(AC)。 A(AB)=A。 A(AB)=A。差差(difference)(d

10、ifference) 2022-3-1215屬于屬于A，但不屬于，但不屬于B的所有元素的所有元素組成的集合叫做組成的集合叫做A與與B的的差，記作差，記作A-B。 A-B=a|aA且且a B “-”為減為減(差差)運算符，運算符，A-B讀作讀作A減減B。 A-A=。 A-=A。 A-B B-A。 A-B=A iff AB=。 A(B-C)=(AB)-(AC)。 |A-B|A|。對稱差對稱差(symmetric difference) 2022-3-1216屬于屬于A但不屬于但不屬于B，屬于，屬于B但不屬于但不屬于A的的所有元素組成的集所有元素組成的集合叫合叫A與與B的的對稱差，記作對稱差，記作A

11、BAB。 AB=a|aAAB=a|aA且且a a B B或者或者a a A A且且aB aB “”為對稱差運算符。為對稱差運算符。ABAB讀作讀作A A對稱減對稱減B B。 AB=(AB)-(AB)=(A-B)(B-A)AB=(AB)-(AB)=(A-B)(B-A)。 笛卡兒積笛卡兒積(Cartesian product) 2022-3-1217A與與B的的笛卡兒積笛卡兒積(Cartesian product)是一個集合，是一個集合，該該集合是由所有集合是由所有這樣這樣的的有序有序?qū)?a，b)組組成的：其中成的：其中aA，bB ，記記作作AB。 AB=(a，b)|aA& bB 。 “

12、”為笛卡兒乘運算符。為笛卡兒乘運算符。AB讀作讀作A叉乘叉乘B。 ABBA。 (AB)CA(BC)。 AAA。 A=。笛卡兒積笛卡兒積(CARTESIAN PRODUCT)2022-3-1218 A(BC)=(AB)(AC)。 (BC)A=(BA)(CA)。 A(BC)=(AB)(AC)。 (BC)A=(BA)(CA)。 A(B-C)=(AB)-(AC)。 (B-C)A=(BA)-(CA)。 當當A、B為有窮集時，為有窮集時，|AB|=|A|*|B|。 冪集冪集(power set) 2022-3-1219A冪集冪集(power set)(power set)是一個集合，該集合是是一個集合，該

13、集合是由由A的所的所有子集組成的有子集組成的，記作，記作2A。 2A=B|B A。 2A讀作讀作A的冪集的冪集。冪集冪集(POWER SET)2022-3-1220 2A。 2A。 2A。 2=。 A2A。 如果如果A是是有窮集有窮集，則，則|2A|=2|A|。 2AB=2A2B。 如果如果A B，則，則2A 2B。 補集補集(complementary set) 2022-3-1221A是論域U上的一個集合，A補集補集是由U中的、不在A中的所有元素組成的集合，記作AUAUU補集補集(COMPLEMENTARY SET)2022-3-1222AABAUBAAB&BABABABAAB U

14、AA如果如果A B，則，則。1.2 1.2 關(guān)系關(guān)系 2022-3-1223二元關(guān)系二元關(guān)系 遞歸定義與歸納證明遞歸定義與歸納證明 關(guān)系的閉包關(guān)系的閉包 1.2.1 二元關(guān)系二元關(guān)系(binary relation) 2022-3-1224二元關(guān)系二元關(guān)系 任意的RAB，R是A到B的二元關(guān)系二元關(guān)系。 。 (a，b) R，也可表示為：aRb。 A稱為定定義義域域(domain)，B稱為值值域域(range)。 當A=B時，則稱R是A上的二元關(guān)系。二元關(guān)系的性質(zhì)二元關(guān)系的性質(zhì)自反(reflexive)性、反自反(irreflexive)性、對稱(symmetric)性、反對稱(asymmetri

15、c)性、傳遞(transitive)性。1.2.1 二元關(guān)系二元關(guān)系(BINARY RELATION)2022-3-1225三歧性三歧性 自反性、對稱性、傳遞性。自反性、對稱性、傳遞性。等價關(guān)系等價關(guān)系(equivalence relation) 具有三歧性的二元關(guān)系稱為等價關(guān)系。等價關(guān)系。 1.2.2 等價類等價類 (equivalence class) 2022-3-1226等價類等價類 (equivalence class) S的滿足如下要求的劃分：的滿足如下要求的劃分：S1、S2、S3、Sn稱為稱為S關(guān)于關(guān)于R的等價劃分，的等價劃分，Si稱為等價類。稱為等價類。 S= S1S2S3Sn

16、； 如果如果ij，則，則SiSj=； 對任意的對任意的i，Si中的任意兩個元素中的任意兩個元素a、b，aRb恒成立；恒成立； 對任意的對任意的i，j，ij，Si中的任意元素中的任意元素a和和Sj中的任意元素中的任意元素b，aRb恒不成立恒不成立 1.2.2 指數(shù)指數(shù)(index)2022-3-1227指數(shù)指數(shù)(index) 把把R將將S分成的等價類的個數(shù)稱為是分成的等價類的個數(shù)稱為是R在在S上的上的指數(shù)指數(shù)。如果如果R將將S分成有窮多個等價類，則稱分成有窮多個等價類，則稱R具有有窮指數(shù)；具有有窮指數(shù)；如果如果R將將S分成無窮多個等價類，則稱分成無窮多個等價類，則稱R具有無窮指數(shù)。具有無窮指數(shù)。

17、給定集合給定集合S上的一個等價關(guān)系上的一個等價關(guān)系R，R就確定了就確定了S的一個的一個等價分類，當給定另一個不同的等價關(guān)系時，它會確等價分類，當給定另一個不同的等價關(guān)系時，它會確定定S的一個新的等價分類。的一個新的等價分類。 1.2.3 關(guān)系的合成關(guān)系的合成(composition)2022-3-1228關(guān)系的合成關(guān)系的合成 (composition) 設(shè)設(shè)R1 AB是是A到到B的關(guān)系、的關(guān)系、R2 BC是是B到到C的關(guān)系，的關(guān)系，R1與與R2的的合成合成R1R2是是A到到C的關(guān)系：的關(guān)系：R1R2=(a，c)| (a，b) R1且且(b，c) R2 。 1.2.3 關(guān)系的合成關(guān)系的合成(co

18、mposition)2022-3-1229 R1R2R2R1。 (R1R2)R3=R1(R2R3)。 (結(jié)合率結(jié)合率) (R1R2)R3=R1R3R2R3。(右分配率右分配率) R3(R1R2)=R3R1R3R2。(左分配率左分配率) (R1R2)R3 R1R3R2R3。 R3(R1R2) R3R1R3R2。1.2.4 遞歸定義與歸納證明遞歸定義與歸納證明2022-3-1230遞歸定義(recursive definition)又稱為歸納定義(inductive definition)，可以用來定義一個集合。集合的遞歸定義由三部分組成：基礎(chǔ)(basis)：用來定義該集合的最基本的元素。歸納(i

19、nduction)：指出用集合中的元素來構(gòu)造集合的新元素的規(guī)則。極小性限定：指出一個對象是所定義集合中的元素的充要條件是它可以通過有限次的使用基礎(chǔ)和歸納條款中所給的規(guī)定構(gòu)造出來。 1.2.4 遞歸定義與歸納證明遞歸定義與歸納證明 2022-3-1231歸納證明歸納證明 與遞歸定義相對應(yīng)。與遞歸定義相對應(yīng)。 歸納證明方法包括三大步：歸納證明方法包括三大步： 基礎(chǔ)基礎(chǔ)(basis)：證明最基本元素具有相應(yīng)性質(zhì)。：證明最基本元素具有相應(yīng)性質(zhì)。 歸納歸納(induction)：證明如果某些元素具有相：證明如果某些元素具有相應(yīng)性質(zhì)，則根據(jù)這些元素用所規(guī)定的方法應(yīng)性質(zhì)，則根據(jù)這些元素用所規(guī)定的方法得到的新

20、元素也具有相應(yīng)的性質(zhì)。得到的新元素也具有相應(yīng)的性質(zhì)。根據(jù)歸納法原理根據(jù)歸納法原理，所有的元素具有相應(yīng)的，所有的元素具有相應(yīng)的性質(zhì)。性質(zhì)。 1.2.4 遞歸定義與歸納證明遞歸定義與歸納證明 2022-3-1232定義定義 1-17 設(shè)設(shè)R是是S上的上的二元二元關(guān)系，我們遞歸地定義關(guān)系，我們遞歸地定義Rn的冪：的冪： R0=(a，a)|aS。 Ri=Ri-1R (i=1,2,3,4,5,)。1.2.4 遞歸定義與歸納證明遞歸定義與歸納證明 2022-3-1233例例1-17 1-17 著名的斐波那契著名的斐波那契(Fibonacci)數(shù)的定義數(shù)的定義 基礎(chǔ)：基礎(chǔ)：0是第一個斐波那契數(shù)，是第一個斐波

21、那契數(shù)，1第二個斐波那契數(shù)；第二個斐波那契數(shù)； 歸納：如果歸納：如果n是第是第i個斐波那契數(shù)，個斐波那契數(shù)，m是第是第i+1個斐波那個斐波那契數(shù)，則契數(shù)，則n+m是第是第i+2個斐波那契數(shù)，這里個斐波那契數(shù)，這里i為大于等于為大于等于1的正整數(shù)。的正整數(shù)。 只有滿足只有滿足(1)和和(2)的數(shù)才是斐波那契數(shù)的數(shù)才是斐波那契數(shù) 0，1，1，2，3，5，8，13，21，34，55，1.2.4 遞歸定義與歸納證明遞歸定義與歸納證明2022-3-1234例例1-18 算術(shù)表達式算術(shù)表達式 基礎(chǔ)：常數(shù)是算術(shù)表達式，變量是算術(shù)表達式；基礎(chǔ)：常數(shù)是算術(shù)表達式，變量是算術(shù)表達式； 歸納：如果歸納：如果E1、E

22、2是表達式，則是表達式，則 +E1、-E1、E1+E2、 E1-E2 、E1*E2 、E1/E2、E1E2、Fun(E1)是是算術(shù)表達式。其中算術(shù)表達式。其中Fun為函數(shù)名。為函數(shù)名。 只有滿足只有滿足(1)和和(2)的才是算術(shù)表達式。的才是算術(shù)表達式。 1.2.4 遞歸定義與歸納證明遞歸定義與歸納證明 2022-3-1235例例1-19 對有窮集合對有窮集合A，證明，證明|2A|=2|A|。證明：證明：設(shè)設(shè)A為一個有窮集合為一個有窮集合, 施歸納于施歸納于|A|： 基礎(chǔ)：當基礎(chǔ)：當|A|=0時時,|2A|=|=1。 歸納：假設(shè)歸納：假設(shè)|A|=n時結(jié)論成立，這里時結(jié)論成立，這里n 0，往證，

23、往證當當|A|=n+1時結(jié)論成立時結(jié)論成立。不妨假設(shè)不妨假設(shè)A=B a，a B 2A=2BCa|C2B 2BCa|C2B= 1.2.4 遞歸定義與歸納證明遞歸定義與歸納證明 2022-3-1236 |2A|=|2BCa|C2B|=|2B|+|Ca|C2B|=|2B|+|2B|=2*|2B|=2*2|B|=2|B|+1=2|A| 由歸納法原理，結(jié)論對任意有窮集合成立。由歸納法原理，結(jié)論對任意有窮集合成立。1.2.4 遞歸定義與歸納證明遞歸定義與歸納證明2022-3-1237例例1-20 1-20 表達式的前綴形式是指將運算符寫在前面，后表達式的前綴形式是指將運算符寫在前面，后跟相應(yīng)的運算對象。如

24、：跟相應(yīng)的運算對象。如：+E1的前綴形式為的前綴形式為+E1，E1+E2的的前綴形式為前綴形式為+E1E2 ，E1*E2的前綴形式為的前綴形式為*E1E2， E1E2的前的前綴形式為綴形式為 E1 E2，F(xiàn)un(E1) 的前綴形式為的前綴形式為Fun E1 。證明例證明例1-18所定義的表達式可以用這里定義的前綴形式所定義的表達式可以用這里定義的前綴形式表示。表示。 1.2.4 遞歸定義與歸納證明遞歸定義與歸納證明 2022-3-1238遞歸定義給出的概念有利于歸納證明。在計算機科遞歸定義給出的概念有利于歸納證明。在計算機科學(xué)與技術(shù)學(xué)科中，有許多問題可以用遞歸定義描述學(xué)與技術(shù)學(xué)科中，有許多問題

25、可以用遞歸定義描述或者用歸納方法進行證明，而且在許多時候，這樣或者用歸納方法進行證明，而且在許多時候，這樣做會帶來許多方便。做會帶來許多方便。 主要是掌握主要是掌握遞歸定義與歸納證明遞歸定義與歸納證明的敘述格式。的敘述格式。 1.2.5 關(guān)系的閉包關(guān)系的閉包 2022-3-1239閉包閉包(closure)(closure) 設(shè)設(shè)P是關(guān)于關(guān)系的性質(zhì)的集合，關(guān)系是關(guān)于關(guān)系的性質(zhì)的集合，關(guān)系R的的P閉閉包包(closure)(closure)是包含是包含R并且具有并且具有P中所有性質(zhì)的最小關(guān)系中所有性質(zhì)的最小關(guān)系。正閉包正閉包(positive closure)(positive closure)

26、 (1)R R+。(2)如果如果(a，b)，(b，c)R+ 則則(a，c)R+。(3)除除(1)、(2)外，外，R+不再含有其他任何元素不再含有其他任何元素。 1.2.5 關(guān)系的閉包關(guān)系的閉包2022-3-1240傳遞閉包傳遞閉包(transitive closure) 具有傳遞性的閉包。具有傳遞性的閉包。R+具有傳遞性。具有傳遞性?？梢宰C明，對任意二元關(guān)系可以證明，對任意二元關(guān)系R， R+= RR2R3R4而且當而且當S為有窮集時：為有窮集時： R+= RR2R3R|S|1.2.5 關(guān)系的閉包關(guān)系的閉包2022-3-1241克林閉包克林閉包(Kleene closure) R(Kleene

27、closure) R* * (1) R R0 0 R R* *,R,R R R* *。 (2) 如果如果(a(a，b)b)，(b(b，c)Rc)R* * 則則(a(a，c)Rc)R* *。 (3) 除除(1)(1)、(2)(2)外，外，R R* *不再含有其他任何元素。不再含有其他任何元素。 自反傳遞閉包自反傳遞閉包(reflexive and transitive (reflexive and transitive closure) closure) R*具有自反性、傳遞性具有自反性、傳遞性。1.2.5 關(guān)系的閉包關(guān)系的閉包2022-3-1242可以證明，對任意二元關(guān)系可以證明，對任意二元關(guān)

28、系R， R*= R0R+ R* =R0RR2R3R4而且當而且當S為有窮集時：為有窮集時： R*= R0RR2R3R|S| 1.2.5 關(guān)系的閉包關(guān)系的閉包2022-3-1243R1、R2是是S上的兩個二元關(guān)系上的兩個二元關(guān)系 (1) +=。 (2) (R1+)+= R1+ 。 (3) (R1*)*= R1*。 (4) R1+R2+ (R1R2)+。 (5) R1*R2* (R1R2)*。 1.3 圖圖2022-3-1244直觀地講，圖是由直觀地講，圖是由一些點一些點和和一些連接兩點的邊一些連接兩點的邊組成。組成。含無方向的邊含無方向的邊的圖為無向圖，的圖為無向圖，含帶有方向的邊含帶有方向的邊

29、的圖的圖為有向圖。為有向圖。 1.3.1 無向圖無向圖 2022-3-1245無向圖無向圖(undirected graph) 設(shè)設(shè)V是一個非空的有窮集合，是一個非空的有窮集合，E VV，G=(V，E)稱稱為為無向無向圖圖(undirected graph)。其中。其中V中的元素稱為中的元素稱為頂頂點點(vertex或或node)，V稱為稱為頂點集頂點集，E中的元素稱為中的元素稱為無無向向邊邊(undirected edge)，E為為無向邊集無向邊集。圖表示圖表示V中稱為頂點中稱為頂點v的元素用標記為的元素用標記為v的小圈表示，的小圈表示，E中的中的元素元素(v1，v2)用標記為用標記為v1，

30、v2的頂點之間的連線表示。的頂點之間的連線表示。 1.3.1 無向圖無向圖2022-3-1246路路(path)如果對于如果對于0ik-1，k1，均有，均有(vi，vi+1)E，則稱，則稱v0，v1，vk是是G=(V，E)的一條長為的一條長為k的的路。路?；芈坊蛉芈坊蛉?cycle)當路當路v0，v1，vk中中v0=vk時，時，v0，v1，vk叫做叫做一個一個回路或圈回路或圈(cycle)。1.3.1 無向圖無向圖2022-3-1247頂點的度數(shù)頂點的度數(shù) 對于對于vV，|w|(v，w)E|稱為無向圖稱為無向圖G=(V，E)的頂點的頂點v的度數(shù)，記作的度數(shù)，記作deg(v)。對于任何一個圖，

31、對于任何一個圖，圖中所有頂點的度數(shù)之和為圖中邊的圖中所有頂點的度數(shù)之和為圖中邊的2倍倍。 VvEv|*2)deg(2022-3-1248deg(v1)=3deg(v2)=3deg(v3)=4deg(v4)=3deg(v5)=3deg(v1)+deg(v2)+deg(v3)+deg(v4)+deg(v5)=16 1.3.1 無向圖無向圖2022-3-1249連通圖連通圖 如果對于如果對于 v，wV，vw，v與與w之間之間至少有一條路至少有一條路存在存在，則稱，則稱G=(V，E)是是連連通通圖圖。 圖圖G是連通的充要條件是是連通的充要條件是G中中存在一條包含圖的所有存在一條包含圖的所有頂點的路頂點

32、的路。 1.3.2 有向圖有向圖 2022-3-1250有向圖有向圖(directed graph) G=(V， ，E)。V：頂頂點點(vertex(vertex或或node)node)集。集。(v1，v2)E：頂點頂點v1到頂點到頂點v2的的有向有向邊邊(directed (directed edge)edge)，或，或弧弧(arc)(arc)，v1稱為稱為前前導(dǎo)導(dǎo)(predecessor)(predecessor)，v2稱為稱為后后繼繼(successor)(successor)。 。有向路有向路(directed path)(directed path) 如果對于如果對于0ik-1，k1

33、，均有，均有(vi，vi+1)E，則稱，則稱v0，v1，vk是是G的一條長為的一條長為k的的有向路。有向路。 1.3.2 有向圖有向圖2022-3-1251有向回路或有向圈有向回路或有向圈(directed cycle) (directed cycle) 對于對于0ik-1，k1，均有，均有(vi，vi+1)E， 且且v0=vk，則稱則稱v0，v1，vk是是G的一條長為的一條長為k的的有向路有向路為為一個一個有向回路。有向回路。有向回路又叫有向圈。有向回路又叫有向圈。 有向圖的圖表示有向圖的圖表示圖圖G G的圖表示是滿足下列條件的的圖表示是滿足下列條件的“圖圖”：其中：其中V V中稱為中稱為頂

34、點頂點v v的元素用標記為的元素用標記為v v的小圈表示，的小圈表示，E E中的元素中的元素(v(v1 1，v v2 2) )用從標記為用從標記為v v1 1的頂點到標記為的頂點到標記為v v2 2的頂點的弧表示的頂點的弧表示。 1.3.2 有向圖有向圖2022-3-1252頂點的度數(shù)頂點的度數(shù) 入度入度( (數(shù)數(shù)) )：ideg(v)=|w|(w，v)E|。 出度出度( (數(shù)數(shù)) )：odeg(v)= |w|(v，w)E|。 對于任何一個有向圖，圖中所有頂點的入度之和與圖對于任何一個有向圖，圖中所有頂點的入度之和與圖中所有頂點的出度之和正好是圖中邊的個數(shù)中所有頂點的出度之和正好是圖中邊的個數(shù)

35、 VvVvEvovi|)deg()deg(2022-3-1253兩個不同的有向圖兩個不同的有向圖1.3.3 樹樹 2022-3-1254滿足如下條件的有向圖滿足如下條件的有向圖G=(V，E)稱為一棵稱為一棵(有序、有序、有向有向)樹樹(tree)： 根根(root) v：沒有前導(dǎo)沒有前導(dǎo)，且，且v到樹中其他頂點均有一條到樹中其他頂點均有一條有向路。有向路。每個非根頂點有且僅有一個前導(dǎo)每個非根頂點有且僅有一個前導(dǎo)。 每個頂點的后繼按其拓撲關(guān)系從左到右排序每個頂點的后繼按其拓撲關(guān)系從左到右排序。 1.3.3 樹樹 2022-3-1255樹的基本概念樹的基本概念 (1) 頂點也可以成為結(jié)點頂點也可以

36、成為結(jié)點。(2) 結(jié)點的前導(dǎo)為該結(jié)點的結(jié)點的前導(dǎo)為該結(jié)點的父親父親(父結(jié)點父結(jié)點father)。(3) 結(jié)點的后繼為它的結(jié)點的后繼為它的兒子兒子(son)。(4) 如果樹中有一條從結(jié)點如果樹中有一條從結(jié)點v1到結(jié)點到結(jié)點v2的路，則稱的路，則稱v1是是v2的的祖先祖先(ancestor), v2是是v1的的后代后代(descendant)。(5) 無兒子的頂點叫做無兒子的頂點叫做葉子葉子(leaf)。(6) 非葉結(jié)點叫做非葉結(jié)點叫做中間結(jié)點中間結(jié)點(interior)。1.3.3 樹樹 2022-3-1256樹的層樹的層 根處在樹的第根處在樹的第1層層(level)。 如果結(jié)點如果結(jié)點v處在第

37、處在第i層層(i1)，則，則v的兒子處在第的兒子處在第i+1層層。樹的最大層號叫做該樹的高度樹的最大層號叫做該樹的高度(height)。 1.3.3 樹樹 2022-3-1257二元樹二元樹 如果對于如果對于 vV，v最多只有最多只有2個兒子個兒子，則稱，則稱G=(V，E)為為二元二元樹樹(binary tree)。 對一棵二元樹，它的第對一棵二元樹，它的第n層最多有層最多有2n-1個結(jié)點。一棵個結(jié)點。一棵n層層二元樹最多有個二元樹最多有個2n-1葉子。葉子。 1.4 語言語言 2022-3-12581.4.1 1.4.1 什么是語言什么是語言 例如：例如：“學(xué)大一生是個我學(xué)大一生是個我”；“

38、我是一個大學(xué)生我是一個大學(xué)生”。 語言是一定的群體用來進行交流的工具語言是一定的群體用來進行交流的工具。 必須有著一系列的生成規(guī)則、理解必須有著一系列的生成規(guī)則、理解(語義語義)規(guī)則規(guī)則。1.4.1 什么是語言什么是語言 2022-3-12591.4.1 什么是語言什么是語言 2022-3-1260斯大林：從強調(diào)語言的作用出發(fā)，把語言定義為斯大林：從強調(diào)語言的作用出發(fā)，把語言定義為“為廣大的人群所理解的字和組合這些字的方法為廣大的人群所理解的字和組合這些字的方法”。 語言學(xué)家韋波斯特語言學(xué)家韋波斯特(Webster) ：為相當大的團體的：為相當大的團體的人所懂得并使用的字和組合這些字的方法的統(tǒng)

39、一體。人所懂得并使用的字和組合這些字的方法的統(tǒng)一體。 要想對語言的性質(zhì)進行研究，用這些定義來建立語要想對語言的性質(zhì)進行研究，用這些定義來建立語言的數(shù)學(xué)模型是不夠精確的。言的數(shù)學(xué)模型是不夠精確的。必須有更形式化的定必須有更形式化的定義義。 1.4.2 形式語言與自動機理論的產(chǎn)生與形式語言與自動機理論的產(chǎn)生與作用作用 2022-3-1261語言學(xué)家喬姆斯基，畢業(yè)于賓西法尼亞大學(xué)，最初語言學(xué)家喬姆斯基，畢業(yè)于賓西法尼亞大學(xué)，最初從產(chǎn)生語言的角度研究語言。從產(chǎn)生語言的角度研究語言。1956年，他將語言年，他將語言L定義為一個字母表定義為一個字母表中的字母組成的一些串的集合：中的字母組成的一些串的集合：

40、 L *。 字母表上按照一定的規(guī)則定義一個文法字母表上按照一定的規(guī)則定義一個文法(grammar)，該文法所能產(chǎn)生的所有句子組成的集合就是該文法該文法所能產(chǎn)生的所有句子組成的集合就是該文法產(chǎn)生的語言。產(chǎn)生的語言。 1959年，喬姆斯基根據(jù)產(chǎn)生語言文法的特性，將語年，喬姆斯基根據(jù)產(chǎn)生語言文法的特性，將語言劃分成言劃分成3大類。大類。 1.4.2 形式語言與自動機理論的產(chǎn)生與形式語言與自動機理論的產(chǎn)生與作用作用 2022-3-12621951年到年到1956年，克林年，克林(Kleene) 在研究神經(jīng)細胞中，在研究神經(jīng)細胞中，建立了識別語言的系統(tǒng)建立了識別語言的系統(tǒng)有窮狀態(tài)自動機有窮狀態(tài)自動機。

41、1959年，喬姆斯基發(fā)現(xiàn)文法和自動機分別從生成和年，喬姆斯基發(fā)現(xiàn)文法和自動機分別從生成和識別的角度去表達語言，而且證明了識別的角度去表達語言，而且證明了文法與自動機文法與自動機的等價性的等價性，這一成果被認為是將形式語言置于了數(shù)，這一成果被認為是將形式語言置于了數(shù)學(xué)的光芒之下，使得形式語言真正誕生了。學(xué)的光芒之下，使得形式語言真正誕生了。 1.4.2 形式語言與自動機理論的產(chǎn)生與形式語言與自動機理論的產(chǎn)生與作用作用2022-3-126320世紀世紀50年代，巴科斯范式年代，巴科斯范式(Backus Nour Form 或或 Backus Normal Form，BNF)實現(xiàn)了對高級語言實現(xiàn)了對

42、高級語言ALGOL-60的成功描述。這一成功，使得形式語言的成功描述。這一成功，使得形式語言在在20世紀世紀60年代得到了大力的發(fā)展。尤其是上下文年代得到了大力的發(fā)展。尤其是上下文無關(guān)文法被作為計算機程序設(shè)計語言的文法的最佳無關(guān)文法被作為計算機程序設(shè)計語言的文法的最佳近似描述得到了較為深入的研究。近似描述得到了較為深入的研究。 相應(yīng)的理論用于其他方面。相應(yīng)的理論用于其他方面。 1.4.2 形式語言與自動機理論的產(chǎn)生與形式語言與自動機理論的產(chǎn)生與作用作用2022-3-1264形式語言與自動機理論在計算機科學(xué)與技術(shù)學(xué)科人才的形式語言與自動機理論在計算機科學(xué)與技術(shù)學(xué)科人才的計算思維的培養(yǎng)中占有極其重

43、要的地位。計算思維的培養(yǎng)中占有極其重要的地位。 計算學(xué)科的主題：計算學(xué)科的主題：“什么能被有效地自動化什么能被有效地自動化”。 1.4.2 形式語言與自動機理論的產(chǎn)生與形式語言與自動機理論的產(chǎn)生與作用作用2022-3-1265計算機科學(xué)與技術(shù)學(xué)科人才專業(yè)能力構(gòu)成計算機科學(xué)與技術(shù)學(xué)科人才專業(yè)能力構(gòu)成 “計算思維能力計算思維能力”抽象思維能力、邏輯思維能力。抽象思維能力、邏輯思維能力。 算法算法設(shè)計設(shè)計與分析能力與分析能力。程序設(shè)計與實現(xiàn)能力。程序設(shè)計與實現(xiàn)能力。計算機系統(tǒng)的認知、分析、設(shè)計和應(yīng)用能力。計算機系統(tǒng)的認知、分析、設(shè)計和應(yīng)用能力。 1.4.2 形式語言與自動機理論的產(chǎn)生與形式語言與自動

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

45、用于后續(xù)課程和今后的研究工作。是進行思維訓(xùn)練的最佳知識載體。是進行思維訓(xùn)練的最佳知識載體。 是一個優(yōu)秀的計算機科學(xué)工作者必修的一門課程。是一個優(yōu)秀的計算機科學(xué)工作者必修的一門課程。 1.4.3 基本概念基本概念 2022-3-1268對語言研究的三個方面對語言研究的三個方面 表示表示(representation) 無窮語言的表示。無窮語言的表示。 有窮描述有窮描述(finite description) 研究的語言要么是研究的語言要么是有窮的，要么是可數(shù)無窮的，這里主要研究可數(shù)無窮有窮的，要么是可數(shù)無窮的，這里主要研究可數(shù)無窮語言的有窮描述。語言的有窮描述。 結(jié)構(gòu)結(jié)構(gòu)(structure)語

46、言的結(jié)構(gòu)特征。語言的結(jié)構(gòu)特征。 1.4.3 基本概念基本概念 2022-3-1269字母表字母表(alphabet) 字母表字母表是一個非空有窮集合是一個非空有窮集合，字母表中的元素稱為該字，字母表中的元素稱為該字母表的一個母表的一個字母字母(letter)。又叫做。又叫做符號符號(symbol)、或者、或者字字符符(character)。非空性非空性。有窮性有窮性。例如：例如： a，b，c，d a，b，c，z 0,1 1.4.3 基本概念基本概念 2022-3-1270字符的兩個特性字符的兩個特性 整體性整體性(monolith)，也叫不可分性。，也叫不可分性。 可辨認性可辨認性(disti

47、nguishable)，也叫可區(qū)分性。，也叫可區(qū)分性。 例（續(xù)）例（續(xù)） a，a，b，b aa，ab，bb ， 1.4.3 基本概念基本概念 2022-3-1271字母表的乘積字母表的乘積(product) 12=ab|a1，b2 例如：例如：0,10,1=00，01，10，11 0,1a，b，c，d=0a，0b，0c，0d，1a，1b，1c，1d a，b，c，d0,1=a0，a1，b0，b1，c0，c1，d0，d1 aa，ab，bb0,1= aa0，aa1，ab0，ab1，bb0，bb1 1.4.3 基本概念基本概念 2022-3-1272字母表字母表的的n次次冪冪 0= n=n-1 是由是

48、由中的中的0個字符組成的。個字符組成的。 的的正閉包正閉包 +=234的的克林閉包克林閉包 *=0+=0231.4.3 基本概念基本概念2022-3-1273例如： 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，

49、abb，abc, 1.4.3 基本概念基本概念2022-3-1274結(jié)論：結(jié)論：*=x|x是是中的若干個，包括中的若干個，包括0個字符，連接而成的一個個字符，連接而成的一個字符串字符串。+=x|x是是中的至少一個字符連接而成的字符串中的至少一個字符連接而成的字符串。1.4.3 基本概念基本概念2022-3-1275句子句子(sentence) (sentence) 是一個字母表，是一個字母表， x*，x叫做叫做上的一個上的一個句子。句子。句子相等。句子相等。 兩個句子被稱兩個句子被稱為為相等的，如果它相等的，如果它們對應(yīng)們對應(yīng)位置上的字符都位置上的字符都對應(yīng)對應(yīng)相相等。等。別稱別稱 字字(wo

50、rd)、 、(字符、符號字符、符號)行行(line)、 、(字符、符號字符、符號)串串(string)。 。1.4.3 基本概念基本概念2022-3-1276出現(xiàn)出現(xiàn)(appearance)x，y*，a，句子，句子xay中的中的a叫做叫做a在該句子中的在該句子中的一個一個出出現(xiàn)現(xiàn)。 。當當x=時，時，a的這個出現(xiàn)為字符串的這個出現(xiàn)為字符串xay的首字符的首字符 如果如果a的這個出現(xiàn)是字符串的這個出現(xiàn)是字符串xay的第的第n個字符，則個字符，則y的的首字符的這個出現(xiàn)是字符串首字符的這個出現(xiàn)是字符串xay的第的第n+1個字符。個字符。 當當y=時，時，a的這個出現(xiàn)是字符串的這個出現(xiàn)是字符串xay的

51、尾字符的尾字符例：例：abaabb。 1.4.3 基本概念基本概念2022-3-1277句子的長度句子的長度(length)(length) x x* *，句子，句子x x中字符出現(xiàn)的總個數(shù)叫做該中字符出現(xiàn)的總個數(shù)叫做該句子的句子的長長度度，記作，記作|x|x|。長度為長度為0 0的字符串叫的字符串叫空句子空句子，記作，記作。 例如：例如： |abaabb|=6 |abaabb|=6 |bbaa|=4 |bbaa|=4 | |=0|=0 |bbabaabbbaa|=11 |bbabaabbbaa|=11 1.4.3 基本概念基本概念2022-3-1278注意事項注意事項是一個句子。是一個句子。

52、 。這是因為。這是因為不是一個空集，它是含有一個空不是一個空集，它是含有一個空句子句子的集合。的集合。|=1，而，而|=0。 1.4.3 基本概念基本概念2022-3-1279并置并置(concatenation) (concatenation) x，y*，x，y的的并置并置是由串是由串x直接相接串直接相接串y所組成所組成的。記作的。記作xy。并置又叫做。并置又叫做連結(jié)連結(jié)。 。 串串x的的n次次冪冪 x0= xn=xn-1x 1.4.3 基本概念基本概念2022-3-1280例如：例如：對對x=001，y=1101 x0=y0= x4=001001001001 y4=110111011101

53、1101對對x=0101，y=110110 x2=01010101 y2=110110110110 x4=0101010101010101 y4=110110110110110110110110 1.4.3 基本概念基本概念2022-3-1281*上的上的并置運算性質(zhì)并置運算性質(zhì) 結(jié)合律：結(jié)合律：(xy)z=x(yz)。 左消去律：如果左消去律：如果xy=xz，則，則y=z。 右消去律：如果右消去律：如果yx=zx，則，則y=z。 唯唯一分解性：存在一分解性：存在唯唯一確定的一確定的a1，a2，an，使得使得x= a1a2an。 單位元素：單位元素：x=x=x。1.4.3 基本概念基本概念20

54、22-3-1282前綴與后綴前綴與后綴 設(shè)x，y，z，w，v*，且x=yz，w=yv (1) y是x的前綴(prefix)。(2)如果z，則y是x的真前綴(proper prefix)。(3) z是x的后綴(suffix)；(4) 如果y，則z是x的真后綴(proper suffix)。(5) y是x和w的公共前綴(common Prefix)。1.4.3 基本概念基本概念2022-3-1283公共公共前綴與后綴前綴與后綴(6)y是x和w的公共前綴，如果x和w的任何公共前綴都是y的前綴，則y是x和w的最大公共前綴。(7) 如果x=zy，w=vy，則y是x和w的公共后綴(common suffi

55、x )。(8) y是x和w的公共后綴，如果x和w的任何公共后綴都是y的后綴，則y是x和w的最大公共后綴。1.4.3 基本概念基本概念2022-3-1284例例 字母表=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 基本概念基本概念2022-3-1285結(jié)論結(jié)論 x的任意前綴的任意前綴y有惟一的一個后綴有惟一的一個后綴z與之對應(yīng)，使得與之對應(yīng)，使得

56、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 基本概念基本概念2022-3-1286結(jié)論結(jié)論 w|w是是x的后綴的后綴=w|w是是x的真后綴的真后綴x， |w|w是是x的后綴的后綴|=|w|w是是x的真后綴的真后綴|+1。 對于任意字符串對于任意字符串w，w是自身的前綴，但不是是自身的前綴，但不是自身的真前綴；自身的真前綴；w是自身的后綴，但不是自身是自身的后綴，但不是自身的真后綴。的真后綴。 對于任意字符

57、串對于任意字符串w，是是w的前綴，且是的前綴，且是w的的真前綴；真前綴；是是w的后綴，且是的后綴，且是w的真后綴的真后綴1.4.3 基本概念基本概念2022-3-1287約定約定 用小寫字母表中較為靠前的字母用小寫字母表中較為靠前的字母a，b，c，表表示字母表中的字母。示字母表中的字母。 用小寫字母表中較為靠后的字母用小寫字母表中較為靠后的字母x，y，z，表表示字母表上的句子。示字母表上的句子。 用用xT表示表示x的倒序。例如，如果的倒序。例如，如果x=abc，則，則xT=cba。 1.4.3 基本概念基本概念2022-3-1288子串子串(substring) (substring) w，x

58、，y，z*，且，且w=xyz，則稱，則稱y是是w的的子串。子串。公共子串公共子串( (common substring)common substring) t，u，v，w，x，y，z*，且，且t=uyv，w=xyz，則稱，則稱y是是t和和w的的公共子串公共子串(common substring)(common substring)。如果。如果y1，y2，yn是是t和和w的公共子串，且的公共子串，且max|y1|，|y2|，|yn|=|yj|，則稱，則稱yj是是t和和w的的最大公共子串。最大公共子串。 兩個串的最大公共子串并不一定是惟一的。兩個串的最大公共子串并不一定是惟一的。 1.4.3 基本概念基本概念2022-3-1289語言語言( (language) language) L *，L稱為字母表稱為字母表上的一個上的一個語語言言(language)(language)， xL，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*， 00，1*1