《形式語言與自動機理論電子教案.ppt》由會員分享，可在線閱讀，更多相關(guān)《形式語言與自動機理論電子教案.ppt（47頁珍藏版）》請在裝配圖網(wǎng)上搜索。

2020/5/31,1,形式語言與自動機理論FormalLanguagesandAutomataTheory,張軍,2020/5/31,2,課程目的和基本要求,課程性質(zhì)技術(shù)基礎(chǔ)基礎(chǔ)知識要求數(shù)學(xué)分析（或者高等數(shù)學(xué)），離散數(shù)學(xué)主要特點抽象和形式化理論證明和構(gòu)造性基本模型的建立與性質(zhì),2020/5/31,3,課程目的和基本要求,本專業(yè)人員4種基本的專業(yè)能力計算思維能力算法的設(shè)計與分析能力程序設(shè)計和實現(xiàn)能力計算機軟硬件系統(tǒng)的認(rèn)知、分析、設(shè)計與應(yīng)用能力計算思維能力邏輯思維能力和抽象思維能力構(gòu)造模型對問題進(jìn)行形式化描述理解和處理形式模型,2020/5/31,4,課程目的和基本要求,知識掌握正則語言、下文無關(guān)語言的文法、識別模型及其基本性質(zhì)、圖靈機的基本知識。能力培養(yǎng)學(xué)生的形式化描述和抽象思維能力。使學(xué)生了解和初步掌握“問題、形式化描述、自動化（計算機化）”這一最典型的計算機問題求解思路。,2020/5/31,5,主要內(nèi)容,語言的文法描述。RLRG、FA、RE、RL的性質(zhì)。CFLCFG(CNF、GNF)、PDA、CFL的性質(zhì)。TM基本TM、構(gòu)造技術(shù)、TM的修改。CSLCSG、LBA。,2020/5/31,6,第1章緒論1.4語言,1.4.1什么是語言例如：“學(xué)大一生是個我”；“我是一個大學(xué)生”。語言是一定的群體用來進(jìn)行交流的工具。必須有著一系列的生成規(guī)則、理解(語義)規(guī)則。,2020/5/31,7,1.4.1什么是語言,2020/5/31,8,1.4.1什么是語言,斯大林：從強調(diào)語言的作用出發(fā)，把語言定義為“為廣大的人群所理解的字和組合這些字的方法”。語言學(xué)家韋波斯特(Webster)：為相當(dāng)大的團(tuán)體的人所懂得并使用的字和組合這些字的方法的統(tǒng)一體。要想對語言的性質(zhì)進(jìn)行研究，用這些定義來建立語言的數(shù)學(xué)模型是不夠精確的。必須有更形式化的定義。,2020/5/31,9,1.4.2形式語言與自動機理論的產(chǎn)生與作用,語言學(xué)家喬姆斯基，畢業(yè)于賓西法尼亞大學(xué)，最初從產(chǎn)生語言的角度研究語言。1956年，他將語言L定義為一個字母表∑中的字母組成的一些串的集合：L?∑*。字母表上按照一定的規(guī)則定義一個文法(grammar)，該文法所能產(chǎn)生的所有句子組成的集合就是該文法產(chǎn)生的語言。1959年，喬姆斯基根據(jù)產(chǎn)生語言文法的特性，將語言劃分成3大類。,2020/5/31,10,1.4.2形式語言與自動機理論的產(chǎn)生與作用,1951年到1956年，克林(Kleene)在研究神經(jīng)細(xì)胞中，建立了識別語言的系統(tǒng)——有窮狀態(tài)自動機。1959年，喬姆斯基發(fā)現(xiàn)文法和自動機分別從生成和識別的角度去表達(dá)語言，而且證明了文法與自動機的等價性，這一成果被認(rèn)為是將形式語言置于了數(shù)學(xué)的光芒之下，使得形式語言真正誕生了。,2020/5/31,11,1.4.2形式語言與自動機理論的產(chǎn)生與作用,20世紀(jì)50年代，巴科斯范式(BackusNourForm或BackusNormalForm，BNF)實現(xiàn)了對高級語言ALGOL-60的成功描述。這一成功，使得形式語言在20世紀(jì)60年代得到了大力的發(fā)展。尤其是上下文無關(guān)文法被作為計算機程序設(shè)計語言的文法的最佳近似描述得到了較為深入的研究。相應(yīng)的理論用于其他方面。,2020/5/31,12,1.4.2形式語言與自動機理論的產(chǎn)生與作用,形式語言與自動機理論在計算機科學(xué)與技術(shù)學(xué)科的人才的計算思維的培養(yǎng)中占有極其重要的地位。計算學(xué)科的主題：“什么能被有效地自動化”。,2020/5/31,13,1.4.2形式語言與自動機理論的產(chǎn)生與作用,計算機科學(xué)與技術(shù)學(xué)科人才專業(yè)能力構(gòu)成“計算思維能力”——抽象思維能力、邏輯思維能力。算法設(shè)計與分析能力。程序設(shè)計與實現(xiàn)能力。計算機系統(tǒng)的認(rèn)知、分析、設(shè)計和應(yīng)用能力。,2020/5/31,14,1.4.2形式語言與自動機理論的產(chǎn)生與作用,,2020/5/31,15,1.4.2形式語言與自動機理論的產(chǎn)生與作用,考慮的對象的不同，所需要的思維方式和能力就不同，通過這一系統(tǒng)的教育，在不斷升華的過程中，逐漸地培養(yǎng)出了學(xué)生的抽象思維能力和對邏輯思維方法的掌握。創(chuàng)新意識的建立和創(chuàng)新能力的培養(yǎng)也在這個教育過程中循序漸進(jìn)地進(jìn)行著。內(nèi)容用于后續(xù)課程和今后的研究工作。是進(jìn)行思維訓(xùn)練的最佳知識載體。是一個優(yōu)秀的計算機科學(xué)工作者必修的一門課程。,2020/5/31,16,1.4.3基本概念,對語言研究的三個方面表示(representation)——無窮語言的表示。有窮描述(finitedescription)——研究的語言要么是有窮的，要么是可數(shù)無窮的，這里主要研究可數(shù)無窮語言的有窮描述。結(jié)構(gòu)(structure)——語言的結(jié)構(gòu)特征。,2020/5/31,17,1.4.3基本概念,字母表(alphabet)字母表是一個非空有窮集合，字母表中的元素稱為該字母表的一個字母(letter)。又叫做符號(symbol)、或者字符(character)。非空性。有窮性。例如：{a，b，c，d}{a，b，c，…，z}{0,1},2020/5/31,18,1.4.3基本概念,字符的兩個特性整體性(monolith)，也叫不可分性。可辨認(rèn)性(distinguishable)，也叫可區(qū)分性。例（續(xù)）{a，a′，b，b′}{aa，ab，bb}{∞，∧，∨，≥，≤},2020/5/31,19,1.4.3基本概念,字母表的乘積(product)∑1∑2={ab|a∈∑1，b∈∑2}例如：{0,1}{0,1}={00，01，10，00}{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},2020/5/31,20,1.4.3基本概念,字母表∑的n次冪∑0={ε}∑n=∑n-1∑ε是由∑中的0個字符組成的?！频恼]包∑+=∑∪∑2∪∑3∪∑4∪…∑的克林閉包∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪…,2020/5/31,21,1.4.3基本概念,例如：{0,1}+={0，1，00，01，11，000，001，010，011，100，…}{0,1}*={ε，0，1，00，01，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,…},2020/5/31,22,1.4.3基本概念,結(jié)論：∑*={x|x是∑中的若干個，包括0個字符，連接而成的一個字符串}?！?={x|x是∑中的至少一個字符連接而成的字符串}。,2020/5/31,23,1.4.3基本概念,句子(sentence)∑是一個字母表，?x∈∑*，x叫做∑上的一個句子。句子相等。兩個句子被稱為相等的，如果它們對應(yīng)位置上的字符都對應(yīng)相等。別稱字(word)、(字符、符號)行(line)、(字符、符號)串(string)。,2020/5/31,24,1.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。,2020/5/31,25,1.4.3基本概念,句子的長度(length)?x∈∑*，句子x中字符出現(xiàn)的總個數(shù)叫做該句子的長度，記作|x|。長度為0的字符串叫空句子，記作ε。例如：|abaabb|=6|bbaa|=4|ε|=0|bbabaabbbaa|=11,2020/5/31,26,1.4.3基本概念,注意事項ε是一個句子。{ε}≠Φ。這是因為{ε}不是一個空集，它是含有一個空句子ε的集合。|{ε}|=1，而|Φ|=0。,2020/5/31,27,1.4.3基本概念,并置(concatenation)x，y∈∑*，x，y的并置是由串x直接相接串y所組成的。記作xy。并置又叫做連結(jié)。串x的n次冪x0=εxn=xn-1x,2020/5/31,28,1.4.3基本概念,例如：對x=001，y=1101x0=y0=εx4=001001001001y4=1101110111011101對x=0101，y=110110 x2=01010101y2=110110110110 x4=0101010101010101y4=110110110110110110110110,2020/5/31,29,1.4.3基本概念,∑*上的并置運算性質(zhì)⑴結(jié)合律：(xy)z=x(yz)。⑵左消去律：如果xy=xz，則y=z。⑶右消去律：如果yx=zx，則y=z。⑷惟一分解性：存在惟一確定的a1，a2，…，an∈∑，使得x=a1a2…an。⑸單位元素：εx=xε=x。,2020/5/31,30,1.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)。,2020/5/31,31,1.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的最大公共后綴。,2020/5/31,32,1.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,2020/5/31,33,1.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的真前綴}|+1。,2020/5/31,34,1.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的真后綴,2020/5/31,35,1.4.3基本概念,約定⑴用小寫字母表中較為靠前的字母a，b，c，…表示字母表中的字母。⑵用小寫字母表中較為靠后的字母x，y，z，…表示字母表上的句子。⑶用xT表示x的倒序。例如，如果x=abc，則xT=cba。,2020/5/31,36,1.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的最大公共子串。兩個串的最大公共子串并不一定是惟一的。,2020/5/31,37,1.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}*,2020/5/31,38,1.4.3基本概念,語言的乘積(product)L1?∑1*，L2?∑2*，語言L1與L2的乘積是一個語言，該語言定義為：L1L2={xy|x∈L1，y∈L2}是字母表∑1∪∑2上的語言。,2020/5/31,39,1.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ù)相同}。,2020/5/31,40,1.4.3基本概念,上述幾個語言的部分特點及相互關(guān)系上述所有語言都是L4的子集(子語言)；L1，L2是有窮語言；其他為無窮語言；其中L1是∑上的所有長度為1的句子組成的語言，L2是∑上的所有長度為2的句子組成的語言；L3，L4分別是∑的正閉包和克林閉包；L5L7≠L6，但L5L7=L8；同樣L9≠L10，但是我們有：L6?L5L7，L9?L10。,2020/5/31,41,1.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，但是0101?L6，1100?L6。而對?x∈L6，有x∈L11。所以，L6?L11。,2020/5/31,42,1.4.3基本概念,L1?L12，L2?L12L5?L12，L6?L12L7?L12，L8?L12L9?L12，L10?L12L1?L10，L2?L10L5?L10，L6?L10L7?L10，L8?L10L9?L10，L10?L12,2020/5/31,43,1.4.3基本概念,例⑴{x|x=xT，x∈∑}。⑵{xxT|x∈∑+}。⑶{xxT|x∈∑*}。⑷{xwxT|x，w∈∑+}。⑸{xxTw|x，w∈∑+}。,2020/5/31,44,1.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∪…,2020/5/31,45,1.5小結(jié),本章簡單敘述了一些基礎(chǔ)知識，一方面，希望讀者通過對本章的閱讀，熟悉集合、關(guān)系、圖、形式語言等相關(guān)的一些基本知識點，為以后各章學(xué)習(xí)作適當(dāng)?shù)臏?zhǔn)備。另一方面，也使讀者熟悉本書中一些符號的意義。,2020/5/31,46,1.5小結(jié),(1)集合：集合的表示、集合之間的關(guān)系、集合的基本運算。(2)關(guān)系：主要介紹了二元關(guān)系相關(guān)的內(nèi)容。包括等價關(guān)系、等價分類、關(guān)系合成、關(guān)系閉包。(3)遞歸定義與歸納證明。,2020/5/31,47,1.5小結(jié),(4)圖：無向圖、有向圖、樹的基本概念。(5)語言與形式語言：自然語言的描述，形式語言和自動機理論的出現(xiàn)，形式語言和自動機理論對計算機科學(xué)與技術(shù)學(xué)科人才能力培養(yǎng)的作用(6)基本概念：字母表、字母、句子、字母表上的語言、語言的基本運算,