形式語言與自動機學(xué)習(xí)小部分內(nèi)容復(fù)述筆記

@[toc]

本文說明

本文內(nèi)容僅僅是稻云麥花（可惡沼头，這幾天因為邪惡的西方勢力無法改昵稱真慘，過了這一段時間我就改昵稱）根據(jù)自己所學(xué)的記憶书劝，盡量不看書或其它的資料瘫证，僅僅憑借鬧鐘記憶和理解，嘗試復(fù)述的筆記庄撮。寫的目的是為了檢驗自己是否真正掌握所學(xué)內(nèi)容背捌。因此，有些東西可能我自覺已經(jīng)是先修課的知識或者是此課程內(nèi)容但是過于簡單基礎(chǔ)無需贅述洞斯。

至于為何不直接說而是以寫下來的方式毡庆，是因為沒有找到一個聽眾，感覺自言自語很神經(jīng)病烙如，并且在自習(xí)室說話估計會被打死么抗。另外寫下來方便自己檢查。同時亚铁，有時候說實際上會比較模糊蝇刀，自己不知道自己在說什么。

至于為什么不用筆寫徘溢，我只想說可能是字太多了吞琐，手要寫斷。好吧然爆，真相是我上次動筆寫字貌似是考試的時候站粟，emmmm....

理直氣壯 表情

其實下次可以帶個筆紙，在湖邊邊說邊寫曾雕，這樣應(yīng)該就不會被打擾自習(xí)室或者圖書館的人了奴烙，說只要是文字，筆寫關(guān)鍵部分的表達式或者圖就好。

溜了溜了 表情

文法

G=<V,T,P,S>

V是變元的集合切诀。

T是終結(jié)符的集合揩环，也就是字母表。

P是產(chǎn)生式幅虑，產(chǎn)生式都是左部推導(dǎo)出右部的形式检盼。產(chǎn)生式都是左部推導(dǎo)出右部的形式，左部右部都是由變元和終結(jié)符并起來的集合中任意選元素組合而成翘单。左部要求至少包含一個變元。

S是變元中的一個特殊元素蹦渣，開始推導(dǎo)變元哄芜，指定從什么變元開始。前三個集合不變柬唯，更換S會導(dǎo)致語言推出來的句子發(fā)生改變认臊。

文法的喬姆斯基分類

文法的喬姆斯基分類是根據(jù)產(chǎn)生是的形式對文法進行分類。

1. 左部右部不施加額外限制就是0型文法锄奢，又稱短語結(jié)構(gòu)文法（PSG）失晴。推導(dǎo)出的文法就是短語結(jié)構(gòu)語言（PSL)。

2. 左部長度不超過右部拘央，就是1型文法涂屁、上下文有關(guān)文法。CSG CSL 上下文有關(guān)語言灰伟。

3. 左部是單個的變元拆又，右部不限制，就是2型文法栏账、上下文無關(guān)文法帖族， CFG CFL 上下文無關(guān)語言

4. 左部是單個的變元，右部是單個的字母或者單個字母連接一個變元挡爵，就是3型文法竖般、正則文法。RG RL 正則語言茶鹃。

有窮自動機 正則語言 正則文法

關(guān)系

正則語言的集合和有窮自動機所能表示的集合是同樣的涣雕。即正則語言和有窮自動機可以互換，是等價的闭翩。而有窮自動機中有確定性有窮自動機DFA胞谭、非確定型有窮自動機NFA、帶空轉(zhuǎn)移的非確定型有窮自動機-NFA男杈。但是他們只是表現(xiàn)和描述形式不一樣丈屹，任意兩個之間都是“等價”的。它們所能表示的語言集合是同一個集合。引入后面兩種自動機是為了方便人構(gòu)造和描述自動機旺垒，而DFA是為了方便證明即計算機自動實現(xiàn)彩库。

正則語言和正則表達式可以互換。

正則表達式

正則表達式先蒋，實際上正則表達式就是集合的操作而已骇钦。只是沒有寫成集合的形式而已。

空集是正則表達式竞漾∶写睿空串或者單獨一個字母表中的字母a都是表示包含一個元素的集合，是正則表達式业岁。

三種操作鳞仙，優(yōu)先級從高到低是閉包運算(*)、連接運算(省略不寫)笔时、并運算（+）棍好。優(yōu)先級相同時自左向右算。

連接運算是兩個集合A與B的相乘允耿，只是得到的結(jié)果集合C的元素不是用<a,b>的序偶表示借笙，而是直接ab直接連接起來，即字符串拼接较锡。

容易知道并（+）可交換可結(jié)合业稼，連接不可交換可結(jié)合。

正則表達式RE->-NFA

基礎(chǔ)情況蚂蕴，空集和單點集容易構(gòu)造有窮自動機盼忌。

對于并操作，A+B掂墓，只需要分別構(gòu)造A和B的有窮自動機谦纱，然后增加一個初始狀態(tài)和接受狀態(tài)。初始狀態(tài)給A和B的初始狀態(tài)各自一個空轉(zhuǎn)移君编，A和B的接受狀態(tài)給都給新增的接受狀態(tài)一個空轉(zhuǎn)移即可跨嘉。 看起來就是“并聯(lián)”電路而已。

對于連接操作符吃嘿， 只需要A的接受狀態(tài)連一條空轉(zhuǎn)移邊到B的初始狀態(tài)即可祠乃。然后初始狀態(tài)設(shè)為A的初始狀態(tài)，接受狀態(tài)設(shè)為B的接受狀態(tài)即可兑燥。 看起來就是“串聯(lián)”電路而已亮瓷。

閉包運算 A*，只需要新增一個初始狀態(tài)和一個接受狀態(tài)降瞳。初始到A初始嘱支，A接受到接受都有一條空轉(zhuǎn)移邊蚓胸。對于原本的A的接受狀態(tài)連一條空轉(zhuǎn)移邊到A的初始狀態(tài)褥民，讓自動機形成一個環(huán)可以不斷打轉(zhuǎn)實現(xiàn)任意正指數(shù)冪的功能镊讼。由于還有一個指數(shù)為0的空串的情況，所以還需要初始到接受增加一條空轉(zhuǎn)移邊俊鱼。

-NFA->NFA(消除空轉(zhuǎn)移邊)

先說空閉包概念汛聚。

空閉包運算 -閉包運算 和

函數(shù)的自變量是一個狀態(tài)锹安，結(jié)果是一個狀態(tài)的集合。如何計算求解呢倚舀？從圖上直觀來講叹哭，就是從q狀態(tài)出發(fā)，只能沿著空轉(zhuǎn)移邊走痕貌，所能走到的所有點（狀態(tài)）就是這個集合中的元素风罩，并且只有這些。當然芯侥，出發(fā)的點q肯定是可以走到的。

和上面這個不同的是乳讥，它的自變量是一個狀態(tài)的集合柱查。運算結(jié)果依舊是一個狀態(tài)的集合。

運算方式就是A集合中的每一個狀態(tài)分別求-閉包云石，然后將這些結(jié)果并起來就是狀態(tài)集合A求空閉包運算的結(jié)果唉工。

當然，你也可以從這些A集合中的點出發(fā)沿著空轉(zhuǎn)移邊去染色汹忠，染上顏色的點就是A這個集合的空閉包運算結(jié)果淋硝。

消除空轉(zhuǎn)移邊得到NFA。

狀態(tài)集合不需要變更宽菜，字母表不需要變更谣膳。初始狀態(tài)也不變。

變的只是轉(zhuǎn)移函數(shù)（也就是畫圖中的邊）和可能需要做調(diào)整的接受狀態(tài)铅乡。

先看初始狀態(tài)的空閉包有沒有接受狀態(tài)继谚，也就是說沿著空轉(zhuǎn)移邊能不能到達接受狀態(tài)。如果有阵幸，那說明去掉空轉(zhuǎn)移邊之后花履，也要接受，加到接受狀態(tài)的集合里即可挚赊。

然后就是轉(zhuǎn)移函數(shù)的變更了诡壁，非常簡單的理解就是，原本-NFA中沿著一條字母值為a的邊到達的狀態(tài)的集合是A荠割，而A的空閉包是B妹卿。那么在NFA中我就需要到B中的每一個狀態(tài)都連一條a邊。原因很簡單，原本的有空轉(zhuǎn)移的自動機里面沿著a邊到達了某個點纽帖，這個點接著一直沿著空轉(zhuǎn)移邊可以走到B中的每一個狀態(tài)那里宠漩，現(xiàn)在把空轉(zhuǎn)移邊去掉了，自然需要補a邊了懊直。

如此扒吁，-NFA消除了空轉(zhuǎn)移邊變成了NFA.

NFA->DFA

NFA是讀入一個字符的時候，一個點出發(fā)可能有多條相同字母值的邊去往不同點室囊。每一次的結(jié)果都是一個狀態(tài)的集合雕崩。初始的結(jié)果是.讀入一個字符a，當前的結(jié)果的每一個點都沿著a邊往后走融撞，只要有就加入到新結(jié)果的狀態(tài)集合中去盼铁。所有字符讀完了，只要結(jié)果的狀態(tài)集合中包含接受狀態(tài)就是接受這個字符串尝偎。

NFA轉(zhuǎn)換成DFA的樸素想法就是饶火，NFA的狀態(tài)集合Q有n個狀態(tài)，那么“結(jié)果的狀態(tài)集合”不就是Q的子集嗎致扯？只需要把Q的每一個子集（共個）都當作DFA的一個狀態(tài)肤寝，然后根據(jù)每一個子集讀不同的字母a在NFA中走出來的新的結(jié)果的狀態(tài)在DFA中連邊即可。

這個是從理論上說明了NFA一定可以變成DFA抖僵。

于是就出現(xiàn)了填表法鲤看。

上面的方法可行，但是會做很多不必要的工作耍群，如有些子集可能在NFA的“行走”中根本不可能出現(xiàn)……

為了避免搞很多多余不必要的狀態(tài)义桂，不必要的邊。

肯定不多余的子集是蹈垢。

對于一個不多余的子集慷吊，我們要順著NFA去走不同字母的邊（如果有的話），去得到子集曹抬。這樣通過非多余的子集走出來子集肯定不是多余的罢浇。

如果最后所有的不多余的子集都走完了。沒有新的子集了沐祷，那么DFA就構(gòu)造完畢了嚷闭。

雖然最壞情況下，可能還是要出現(xiàn)級別個狀態(tài)赖临，但是胞锰，實際應(yīng)用的時候，很多情況下DFA的狀態(tài)數(shù)并不是增長太多兢榨。

DFA->正則表達式

一種是類似于FLOYD的思想（我一下也不知道哪個先出的嗅榕，我只知道我接觸的是FLOYD）顺饮。限制中間點不能超過k，然后逐步將k變大凌那，當k到達n只是就是沒有限制了兼雄。

DFA的狀態(tài)從1編號到n.

是一個正則表達式。這個正則表達式表示的語言是：從自動機的狀態(tài)i出發(fā)帽蝶，到達狀態(tài)j赦肋，并且中間（不包含i,j）經(jīng)過的狀態(tài)的編號都不超過k。

初始化（邊界情況是k=0的時候）:

若

1. i到j(luò)沒有邊励稳，表達式是

2. i到j(luò)只有一條邊佃乘，字母值為a的邊，則表達式是

3. i到j(luò)只有多條邊驹尼，則表達式是這些邊的并

若,則i到j(luò)的字符串還可以是空串趣避，因此，上面三種情況都需要并上空串

迭代方式（轉(zhuǎn)移方程）

解釋：

1. 中間點根本就不經(jīng)過k新翎，那么就是k-1限制下所表示的

2. 中間點經(jīng)過了k程帕，那么就是三段，前面一段是i到k（沒有經(jīng)過k地啰，故事k-1限制下的）愁拭，后面一段是k到j(luò)。中間是k到k的重復(fù)若干次（0,1,2,3,..次）髓绽，故就是閉包敛苇。三段連接起來即可妆绞。

DFA->正則表達式的狀態(tài)消除法

大體就是邊上不在寫字母顺呕，而是寫正則表達式。

畫圖比較容易說明括饶。

消除單個狀態(tài)

消除一個狀態(tài)并消除影響（補償）的方法株茶。

因此只需要考慮前驅(qū)，自身（自環(huán)）图焰，后繼的問題启盛。 拆分成三段，前驅(qū)到自身技羔，自身自環(huán)轉(zhuǎn)轉(zhuǎn)轉(zhuǎn)（閉包）僵闯，自身到后繼 這個用正則表達式表示出來并到前驅(qū)到后繼里面即可。

整體消除方法

目標藤滥，僅僅保留初始狀態(tài)和接受狀態(tài)鳖粟。（如果初始狀態(tài)剛好就是接受狀態(tài)，就只剩下一個狀態(tài)了）拙绊。

對于消除到最后的自動機就好表示成正則表達式了向图。

先不斷消除既非初始狀態(tài)也非接受狀態(tài)的狀態(tài)泳秀。 因為這樣無需分類，消除了它榄攀，沒有影響嗜傅。

接著要消除接受狀態(tài)了，這個必須分支檩赢。 例如消除s吕嘀，雖然每個前驅(qū)s到后繼q的路徑補償了，但是消除掉s之后漠畜，初始狀態(tài)經(jīng)s到其它接受狀態(tài)的是可以表示币他，但是只走到s的理論上也要接受，但是s消除了無法接受憔狞。因此蝴悉，要分支。

怎么分支或者說消除的順序瘾敢？

例如剩余m個接受狀態(tài)p,q,r,s,t,...

• 將p視作唯一接受狀態(tài)拍冠，不斷消除“非接受狀態(tài)”，因此我們得到了僅僅到p的接受狀態(tài)的自動機簇抵；

• 消除p的時候庆杜，我們丟失了僅僅到p應(yīng)該接受的表達式。但是到其它的狀態(tài)沒有丟失碟摆，至此晃财，我們的需要求解的“接受狀態(tài)的數(shù)目”縮小了1。

最后我們會得到m個簡單的自動機典蜕。分別是僅僅接受到狀態(tài)p,q,r,s,t...的自動機

它們的表達式取并即可断盛。

DFA最小化

DFA最小化就是將任意的DFA轉(zhuǎn)換為等價的最小化的DFA（狀態(tài)數(shù)最少）.

最小化的DFA中任意兩個狀態(tài)都是可區(qū)別的。

狀態(tài)可區(qū)別 可區(qū)別狀態(tài)對 等價狀態(tài)

兩個狀態(tài)q和p愉舔。

如果存在某一個字符串钢猛，分別從p和q出發(fā)，p和q走出來的結(jié)果（接受或拒絕）不一樣轩缤，那么p和q就是可去別的狀態(tài)對命迈。

與之相對的概念是狀態(tài)等價。即無論什么字符串火的，從p和q出發(fā)壶愤，走出來的結(jié)果都是一樣的，要么都是接受馏鹤，要么都是拒絕征椒。對于等價狀態(tài)，顯然直觀上我們想讓它們合并讓狀態(tài)數(shù)變少假瞬。

如何確定哪些狀態(tài)兩兩可區(qū)分

當然陕靠，我們可以直接自己構(gòu)造一個字符串迂尝，讓兩個狀態(tài)走出來的結(jié)果不一樣說明它們不可區(qū)分；但是剪芥，如果以下沒有構(gòu)造出來可以走出不同的字符串垄开，那么就無法確定了；更糟糕的是是如果兩個狀態(tài)是等價的税肪，那么通過構(gòu)造字符串溉躲，我們肯定是得到結(jié)果是一樣的，但是我們有不能直接肯定任意字符串益兄，得到結(jié)果都是一樣的锻梳，那么它們到底是不是可區(qū)分的就解決不了了。

因此净捅，我們需要一定的方法疑枯。

1. 接受狀態(tài)和非接受狀態(tài)肯定是不等價的，即可區(qū)分的蛔六。

2. 如果對于同一個字母邊荆永，p和q走出的狀態(tài)不等價，那么p和q不等價国章。要斷言p和q不等價具钥，要p和q沿著某一個字母值的邊到達的狀態(tài)中有兩個不等價就可以了；如果要斷言等價液兽，就要各個字母的邊邊走到的狀態(tài)都是等價的才行骂删。

有了這兩條之后，我們就可以運用填表法來確定了四啰∧担√ × ？（待定）

一輪一輪的掃描拟逮，如果某一輪之后沒有新增的可區(qū)分對撬统，那么說明所有的可區(qū)分對都找出來了适滓。

然后把等價的狀態(tài)合并成一個敦迄，等價狀態(tài)內(nèi)部的邊變成自環(huán)邊，入邊出邊進行整合合并凭迹，over罚屋。

正則語言的性質(zhì)

泵引理

其實泵引理就是根據(jù)鴿籠原理，對于一個狀態(tài)數(shù)為n的DFA嗅绸，讀完長度大于等于n的字符串w之后脾猛，必然至少有一個狀態(tài)被訪問了兩次，換句話說鱼鸠，出現(xiàn)了一個環(huán)猛拴。然后對于那個環(huán)羹铅，可以不走，走1次愉昆，走2次职员，走3次……

因此,可以把這個環(huán)所對應(yīng)的字符子串v去掉或重復(fù)若干次，得到的新字符串依舊和原本的結(jié)果是一樣的（接受或拒絕）跛溉。

,.

正則語言的泵引理敘述的是正則語言的性質(zhì)。它的作用是芳室，對于一個語言L专肪，常常通過正則語言的泵引理來推導(dǎo)出矛盾（某個不應(yīng)該接受的字符串被接受了），從而說明這個語言L不是正則語言堪侯。但是嚎尤，通過正則語言的泵引理是無法證明一個語言是正則語言的，畢竟泵引理只是正則語言的必要條件（性質(zhì)）伍宦，而非充分條件诺苹。

正則語言的判定

1. 正則語言的判定，即斷言一個語言是正則語言雹拄，通常是構(gòu)造一個-NFA（或NFA收奔、DFA）接受這個語言或者構(gòu)造正則表達式（基于的理論是已經(jīng)證明了這些都是等價的……）。

2. 根據(jù)已知的正則語言（可以通過第1條迅速證明）的正則語言及正則語言的封閉性（并滓玖、交坪哄、差、補势篡、反轉(zhuǎn)翩肌、閉包、連接禁悠、同態(tài)念祭、逆同態(tài)）來做運算得到要證明的語言L是正則語言。

二〇一九年六月六日

稻云麥花