1、第四部分是形式語言和自動機的理論基礎(chǔ)。眾所周知，計算機是數(shù)學(xué)和電子學(xué)結(jié)合的產(chǎn)物，它的數(shù)學(xué)模型是圖靈定義的計算模型。在當今的信息社會，計算無處不在，每個人都在計算，計算影響著每個人。計算機科學(xué)在這個信息社會中發(fā)揮著越來越重要的作用。計算機科學(xué)有許多基礎(chǔ)理論，但計算模型的基礎(chǔ)理論主要包括形式語言和自動機理論、可計算性理論、邏輯和程序設(shè)計理論。形式化和抽象是計算機科學(xué)理論的重要特征。本文主要介紹計算模型基礎(chǔ)理論中的形式語言和自動機理論。第二十三章形式語言、符號和符號串是形式語言中非常重要的基本概念。象征主義在計算機科學(xué)的發(fā)展中一直占據(jù)著非常重要的地位。語言以字母表為基礎(chǔ)。23.1符號，符號串及其操作

2、，字母表：一個非空的有限集合被稱為字母表，它通常由西方字母表示或大寫。字母表中的元素被稱為字母或符號，通常由小寫字母和數(shù)字表示。符號串：符號串是由字母表中的字母組成的有限序列。符號串長度：符號串中包含的符號數(shù)稱為符號串長度。符號串w的長度表示為|w|。空字符串：長度為0的符號字符串稱為空字符串，由。連接是符號串的基本操作。兩個符號串X和y的并集，表示為XY，是在X后面跟隨y形成的符號串.符號串的連接：讓=1，2是一個字母表。讓X=11和Y=22是上的兩個符號串。那么：XY=1122是兩個符號串x和y的連接，XY是一個符號串on。YX=2211是兩個符號串y和x的連接，YX也是世界上的一個符號串

3、。一般來說，符號串的連接不滿足交換定律。顯然，符號串的連接滿足關(guān)聯(lián)定律，即，(XY)Z=X(YZ)。在上面的例子中，顯然有XYYX，(XY)X=X(YX)=112211。因為它是一個沒有符號的符號串(空串)，它存在于任何符號串X中，X=X=X.因此，我們可以把它看作是符號串聯(lián)運算的單位元。假設(shè)x是一個符號串，在連接x本身n次后，符號串Z，也就是，Z=XXXX=Xn，被稱為x的冪。我們同意X0=。這個定義可以遞歸地表示為：符號串的冪：符號串v是符號串W的子串，當且僅當有符號串x和y，所以W=XVY。這里，x和y都可以是空字符串。如果x和y都是，顯然W=V，那么每個符號串都是它自己的子串。如果X=

4、，v是w的前綴，如果同時有Y，v是w的真前綴。如果Y=，v是w的后綴，如果同時有X，v是w的真后綴，符號串的子串、前綴和后綴：讓A和B都是符號串的集合， 并且設(shè)集合A和集合B之間的連接為AB=XY | XA和YB，即集合A和集合B之間的連接是集合A中的符號串和集合B中的符號串之間的連接形成的集合。設(shè)A為一組符號串，在A本身被連接n次之后，新的集合A，即安=AAA，被稱為集合A的冪。我們同意A0=1。 這個定義可以遞歸地表示為：集合的冪：設(shè)A是符號串的集合，用A*表示A的所有有限冪的并集，那么A*稱為集合A上的閉包，即A*=A0 A12an稱為集合A上的正閉包，顯然，有A*=A0 A，A * A

5、=AA *。注意：閉包A*和正閉包A之間的區(qū)別在于它是否包含空字符串。當空字符串從閉包A*中移除后，它就變成了正閉包A。A *有一個可數(shù)的無限個符號字符串。集合的閉包和正閉包：使它成為一個字母表。如果L *，那么L是字母表中的一種語言。也就是說，l是由字母表上的字符串組成的集合。語言：語言是用語法來描述的。語法實際上是一套有限的規(guī)則。這些正則表達式給出了語言中的各種語法元素以及它們?nèi)绾螛?gòu)成句子。為了定義正則表達式，需要引入一類新的符號，即語法符號。23.2語法和語言的正式定義。為了區(qū)分字母表上的符號和語法符號，我們分別稱它們?yōu)榻K止符和非終止符。終結(jié)符：一種語言字母表中的符號。讓我們把它寫下來。

6、非終結(jié)符(一個過渡符號):它也是一個符號，但不是字母表中的一個符號。讓我們把它記為V。對于形式語言L，讓T和V是它的終止符集和非終止符集，顯然有L T*，和TV=，語法符號，定義23.1:一個產(chǎn)品是一個有序?qū)?，)，它通?？梢詫懗上旅娴男问?或其中：V，V*，V=VT。生產(chǎn)的左邊部分稱為生產(chǎn)的右邊部分。注意：V是非終止符，也就是說，產(chǎn)品的左邊部分不允許是空字符串。V*表示產(chǎn)品的右邊部分是這樣一個符號字符串，它可以包含終止符、非終止符和空字符串。語法的正式定義，定義23。語法G被定義為四重G=(V，t，p，s)，其中：1。v是一個非空的有限集，稱為非終集。2.t是一個非空的有限集，稱為終止集，V

7、T=1。3.p是一組非空的有限生產(chǎn)表達式。4.SV被稱為語法的開始符號，s應(yīng)該作為至少一個生產(chǎn)中的左邊部分出現(xiàn)在P中，語法的形式定義，例23.6讓語法G=(A，E，A，P，A)，其中P=Aa，A aE，E aA。在許多語法中，有許多左部相同的生產(chǎn)形式，所以左部相同的生產(chǎn)形式可以寫成組合生產(chǎn)形式。在這個示例方法g中，P中前兩個表達式的左邊部分是相同的，都是A，可以組合成A | A | aE，因此P=A a | aE，E=aA。在很多情況下，你只需要寫出語法的產(chǎn)出來展示語法。慣例：第一個生成的左邊部分是語法的開始，語法的正式定義，定義23.3:給定一個語法G=(V，T，P，S)，如果它是G中的一個

8、生成，并且是V*中的任何符號，如果有一個符號串X，y滿足：x=，y=，那么X使用該生成直接生成y。派生的形式定義，定義23.4:給定一個語法G=(V，T，P，S)，讓x，yV*，如果：1，有下面的直接派生序列：x=w0 w1 w2 wn=y(n0)，那么x被調(diào)用來派生(產(chǎn)生)y，并且派生長度為n，或者y被簡化為x. 2。我們用x，y來表示n0和x，n，y的存在。X*y表示x y或x=y.最左邊(右邊)的派生：如果在x中最左邊(右邊)的非終止符在派生的每一步都被生產(chǎn)所取代，那么這個派生稱為最左邊(右邊)的派生。最右邊的推導(dǎo)也稱為規(guī)范推導(dǎo)。定義23。5:給定一個語法G=(V，T，P，S)，如果符號

9、串x是從語法G的起始符號S，即S *x派生出來的，那么x稱為語法G的句型。如果符號串x是一個只由終止符組成的句型，即S*x和xT*，那么x是一個語法G的句子。從規(guī)范派生出來的句型稱為規(guī)范句型。標準句型，定義23。設(shè)GS是一個語法，x=w是一個句子類型，如果：S*A和A * w，那么W是相對于非終止符A的句型X的一個短語；如果：S*A和Aw，w是句型x相對于非終結(jié)符的直接短語(或簡單短語)；如果w是句型x的最左邊的直接短語，w被稱為句型x的句柄，短語，直接短語和句柄，定義23.7:給定語法G=(V，T，P，S)，由G生成的語言被表示為L(G)，讓L(G)=x | S x和xT*，其中x被稱為語言

10、L(G)的句子。也就是說，L(G)是一個由所有句子組成的集合，從語法G的起始符號S派生而來，語言的形式定義，例23.8給定語法GS:S aSb | ab由這個語法生成的任何句子是：首先用產(chǎn)生式S aSb幾次得到：S AsB AASB an-1S bn-1，即San-1sBN-1；然后，公式S ab被使用一次以獲得：S an-1S bn-1 anbn。用數(shù)學(xué)歸納法證明從這種語法中導(dǎo)出的所有符號串都是anbn形式并不難。另一方面，用數(shù)學(xué)歸納法證明符號串的長度并不難。任何形式為anbn，n1的符號串都可以通過語法GS推導(dǎo)出來，也就是說，有派生的ANBN。因此，L(GS)=anbn | n1。例23.

11、9設(shè)置語法gv: v AVB，Vb bW，abW c.找到由語法GV生成的語言。解答：V是語法的開始。該公式被多次使用，推導(dǎo)結(jié)果為anVbn，n1。在anVbn中，為了消除非終止符v，必須使用生產(chǎn)公式VbbW，推導(dǎo)結(jié)果為：AnBbn-1=an-1 Bwbn-1，n1。只有利用生成公式abWc，才能剔除非終止子w，最終得到推導(dǎo)結(jié)果：an-1cbn-1，n1。另一方面，也不難證明任何形式為ancbn和n0的符號串都可以通過語法GV推導(dǎo)出來。因此，由語法GV生成的語言是L(GV)=an-1cbn-1 | n1=ancbn | n0。示例23.10語法ga: AAR、Aab、RAb生成語言L(GA)=

12、anbn | n1。從上面可以看出，盡管示例23.7中的語法GA和語法GS是兩種不同的語法，但是生成的語言是相同的，并且它們都是n | n | 1。定義1.8給定任意兩個文法G1和G2，如果它們產(chǎn)生相同的語言，即L(G1)=L(G2)，那么G1和G2的文法是等價的。語法樹是句型推導(dǎo)的圖形表示。例如，假設(shè)句子bd0的最右邊的派生或規(guī)范派生是：0 0 d0 d0 bd0，語法樹，定義1.9如果一個語法有兩個以上不同的語法樹對應(yīng)于一個句子，或者有兩個以上不同的最左邊(右邊)派生，那么這個語法就被認為是不明確的(編程語言不能是不明確的)。定義1.10如果語言L的任何語法是二元語法，那么語言L就是二元語

13、言。理論上，已經(jīng)證明了這種模糊語言的存在。語法歧義和語言歧義是兩個不同的概念。1956年，喬姆斯基將語法分為四種類型：0型語法、1型語法、2型語法和3型語法。這種語法分類被稱為喬姆斯基分類。根據(jù)語法的四種類型，語法生成的語言也分為四種類型，即0型語言、1型語言、2型語言和3型語言。喬姆斯基建立的形式語言理論對計算機科學(xué)的發(fā)展產(chǎn)生了深遠的影響，尤其是對計算機編程語言的設(shè)計、編譯方法和計算復(fù)雜性的影響。語法和語言類型，定義1.12讓語法G=(V，T，P，S)，如果P滿足| | | |(S除外)，那么語法G被稱為類型1語法或上下文相關(guān)語法，縮寫為CSG。類型1語法的產(chǎn)生形式也被描述為：1A212，其

14、中：1，2，(VT)，反病毒。它能更好地反映“語境相關(guān)”的含義，因為只有A出現(xiàn)在1和2之間(1在A之上，2在A之下)，它被允許代替A。由類型1語法產(chǎn)生的語言被稱為類型1語言或語境相關(guān)語言(簡稱CSL)。類型1語法，定義1.13讓語法G=(V，T，P，S)，如果對于P滿足V，(VT)*，那么G稱為類型2語法或上下文無關(guān)語法，縮寫為CFG。上下文無關(guān)語法被命名為“上下文無關(guān)”的原因是字符總是可以被字符串自由替換，而不考慮字符出現(xiàn)的上下文。由類型2語法產(chǎn)生的語言被稱為類型2語言或上下文無關(guān)語言(簡稱CFL)。上下文無關(guān)語法的一個簡單例子是S-aSb |。由于這種語法的生成在左邊有一個非終結(jié)符S，在右

15、邊有一個由終結(jié)符或非終結(jié)符組成的符號串a(chǎn)Sb和，因此它滿足了上下文無關(guān)語法生成的要求。這種語法產(chǎn)生的語言是ann :n 0。類型2語法，定義1.14:讓語法G=(V，T，P，S)，如果P中的每個產(chǎn)品都是AaB或Aa，其中：a，BV，aT，那么G稱為類型3語法或普通語法，縮寫為r G。由類型3語法產(chǎn)生的語言被稱為類型3語言或正常語言(縮寫為RL)。類型3語言相當于有限自動機，也就是說，有限自動機可以識別類型3語言。在忽略句子的情況下，根據(jù)喬姆斯基的分類定義，任何類型3語言都是類型2語言，任何類型2語言都是類型1語言，任何類型1語言都是類型0語言。喬姆斯基層次的形式語言，范式是由較簡單的范式按照一

16、套定義規(guī)則組成的，而每一個范式e代表一種語言L(e)(范式集)。定義1.15字母表上的正規(guī)表達式和正規(guī)集遞歸定義如下：1 .任何一個A都是字母表上的正規(guī)表達式，它所代表的正規(guī)集合是a2?？兆址巧系恼１磉_式，它所代表的正常集是。3.符號是上的正常表達式，它所代表的正常集是。23.3正常表達；4.設(shè)e1和e2都是上的正規(guī)表達式，它們所代表的正規(guī)集是L(e1)和L(e2)，那么(1)e1 e2也是正規(guī)表達式，它所代表的正規(guī)集是L(e1 e2)=L(e1)L(e2) (2)e1e2也是正規(guī)表達式。它所代表的正規(guī)集是L(e1e2)=L(e1)L(e2) (3)(e1)*，這也是一個正規(guī)表達式。它所

17、代表的正規(guī)集是L(e1)*)=(L(e1)*，示例23.14使=A，B。下表列出了上的一些正規(guī)表達式和相應(yīng)的正規(guī)表達式。下一個優(yōu)先級是“連接”運算符，它類似于代數(shù)運算中的乘法。最低優(yōu)先級是“與”操作(運算符)。它類似于代數(shù)運算中的加法。您可以通過在正則表達式中添加括號來更改操作的優(yōu)先級。正常表達式運算符的優(yōu)先順序，一種正常語言可以由正常語法或正常形式來定義，而對于任何正常語法，都有一種正常形式來定義同一種語言；相反，對于每一種正常的形式，都有一種正常的語法產(chǎn)生相同的語言。正規(guī)表達式和正規(guī)語法可以相互轉(zhuǎn)換。23.4正常語法和正常表達，將正常表達r轉(zhuǎn)換為正常語法G=(V，t，s，p)的方法如下：1 .讓t=；