自动机理论、形式语言和计算导论提纲
我真的是覺得這門課太虛了。。這個總結基于名教材《自動機理論、語言和計算導論》（機械工業(yè)），也可以說是這本書的總結。由于這門課里很多羅馬字母，打字很困難所以能省略的公式都不寫了，可以算是入門介紹了。這里省略的內(nèi)容，看看書就明白了。
A. 概念入門
1.有窮自動機：對于一個系統(tǒng)，如果說他有有限個狀態(tài)，在這些狀態(tài)間響應外部輸入并按照一定規(guī)則切換，又能記憶當前狀態(tài)，則稱該系統(tǒng)為有窮自動機。比如一個開關。有開和關兩態(tài)，如果當前態(tài)為開，撥動開關狀態(tài)將成為關，反之亦然。所以開關是一個有窮自動機。
2.形式化證明：計算機也可以認為是復雜的自動機，對于一個自動機系統(tǒng)能夠做什么并不顯而易見，比如人們認為很多事情是計算機無法實現(xiàn)的。為了驗證這種可能性避免無用功，引入了形式化證明的概念。包括演繹證明和歸納證明。分別對應我們高中學過的一般證明和歸納法。技巧包括反證法等等。
3.自動機理論的中心概念：就是字母表，串和語言。顧名思義字母組成串（句子），串組成語言。
看看這些東西覺得這門課真夠虛。。。= =
B.有窮自動機的分類
我們知道有窮自動機之所以有窮，是說其狀態(tài)有限，但是在某個時刻自動機能否只處于一個狀態(tài)來看，有窮自動機可以分為確定型和非確定型有窮自動機。后者可以利用算法“編譯”成前者。
1.確定型有窮自動機（DFA）：有有窮狀態(tài)集合和輸入符號集合，轉(zhuǎn)移函數(shù)，初始狀態(tài)，以及一個終結狀態(tài)集合。表示為 。DFA的狀態(tài)圖：用箭頭來表示狀態(tài)間的轉(zhuǎn)換，用圓圈+文字表示狀態(tài)，用一個同心圓表示終結狀態(tài)，用start表示開始狀態(tài)。狀態(tài)表：可以想象。
2.DFA上的語言——正則語言：正則語言定義為讓初始狀態(tài)到達一個結束狀態(tài)的串的集合。
這個串必須能滿足DFA的轉(zhuǎn)移函數(shù)，也就是自動機改變狀態(tài)的那個規(guī)則。為了讓這個函數(shù)能夠處理一串輸入，我們假設xa是一個以a結尾的串，并且σ是處理一個狀態(tài)和一個輸入的函數(shù)，σ0為一個狀態(tài)和一串輸入的函數(shù)，那么σ0(q,xa)=σ(σ0(q,x),a)。如果學過動態(tài)規(guī)劃，這個和狀態(tài)轉(zhuǎn)移函數(shù)很像，不難理解。如果假設σ0(q,x)=p,那么相當于σ0(q,xa)=σ(p,a)，可以用這個思想逐步分解一個串輸入。
3.非確定型有窮自動機（NFA）：可以說是另一種看事物的角度吧。舉個例子，要接受所有以01結尾的字串，用q0表示開始搜索狀態(tài)，q1表示找到了一個0的狀態(tài)，q2表示緊接著找到了1（也就是說查找結束）。對于q0來說，如果下一個符號是1，他必須返回自身，因為這肯定不是我們要找的01結尾，如果下一個是0，他也不一定就是結尾的那個0，也可以返回自身，但是畢竟他是0，所以一旦找到一個0，就是可以進入狀態(tài)q1了。也就是說，對于輸入0來說，可以處在q0q1兩個狀態(tài)，所以就是NFA了。NFA也可以擴展轉(zhuǎn)移函數(shù)σ
4.NFA和DFA的等價性。任何NFA都可以用DFA描述，但是狀態(tài)可能略多。下面通過一個例子來看看怎么轉(zhuǎn)化
?
下面是一個NFA狀態(tài)表0 1
->p {p,q} {p}
q {r} {r}
r {s} Φ
*s {s} {s}
算法是，初始狀態(tài)為p，他指向兩個狀態(tài)，我們把{p,q}作為一個狀態(tài)考慮，輸入0的時候，p->{p,q},q->{r},也就是說{p,q}->{p,q,r}，同理輸入1時{p,q}->{p,r}。終結狀態(tài)是S，
而包含s的狀態(tài)集包括{s},{ps},{pqs},{qs},{rs},{prs},{qrs},{qprs}，這些都是DFA的終結狀態(tài)，但是其中很多不可能達到。
相信大家已經(jīng)知道怎么算了A = {p}; B = {p,q}; C = {p,r}; D = {p,q,r}; E = {p,q,s}; F = {p,q,r,s}; G = {p,r,s}; H = {p,s}.0 1
->A B A
B D C
C E A
D F C
*E F G
*F F G
*G E H
*H E H
?5.帶ε轉(zhuǎn)移的有窮自動機
這種自動機的思想就是允許無條件狀態(tài)轉(zhuǎn)向。舉例，在一串字符中查找字符串web和ebay，可以將任意字符狀態(tài)定義成q0，將進入查找A設為q1，查找B設為q2。q0到q1q2是無條件的帶ε轉(zhuǎn)移，因為這三個狀態(tài)都沒有觸發(fā)關鍵字（比如w和e），都是任意字符輸入狀態(tài)。
ε閉包ECLOSE(P)定義為從狀態(tài)P通過ε通路能到達的所有狀態(tài)（包括P）的集合。從上面的描述可以看出ε轉(zhuǎn)移是可以消去的（比如我們可以不定義q1q2，直接設置一個觸發(fā)w的狀態(tài)q3和觸發(fā)e的狀態(tài)q4）。具體的方法看課本P55-56
C.正則表達式
1. 運算符：取并的+運算，連接，*是正則表達式的三種基本運算。*代表任意數(shù)量個他左邊的單位。
比如：字母表{a,b,c}上至少一個a和至少一個b的集合：分析一下，如果a在b之前，那么出現(xiàn)第一個a之前，可以有任意個c，即為c*，隨后出現(xiàn)1個a，任意數(shù)量的a或c（或的概念往往通過取并表示），然后出現(xiàn)一個b，后面的字符串就可以隨便取a或b或c，那么表達為c*a(a+c)*b(a+b+c)*，類似b在a前面也一樣，最終結果是c*a(a+c)*b(a+b+c)* + c*b(b+c)*a(a+b+c)*
2.正則表達式的代數(shù)定律
把這個放到前面來會讓問題更簡單。除了一些結合律交換律分配律等等大家可以自己衡量對錯的數(shù)學定律，此外：
ε稱作單位元，εR=Rε=R. Φ稱作零元。?Φ*R=R*Φ=Φ,Φ+R=R。此外還有冪等律L+L=L，(L*)*=L*, Φ*=ε,ε*=ε
2.將DFA轉(zhuǎn)化為正則表達式
這個算法有點惡心所以花點篇幅。把DFA的狀態(tài)用自然數(shù)1~N表示，定義一個正則表達式Rij(K),表示DFA中從狀態(tài)i到j且中間不經(jīng)過大于k的節(jié)點的輸入串，另外i=j的時候考慮到一個狀態(tài)的ε轉(zhuǎn)移就是它自身，所以ε也是一個符合要求的串。拿我們上面用的那個DFA的圖來看，R00(0)=ε+b,R01(0)=b。
確定了k=0的情況，就可以用歸納法了。我們來考慮k時的情形，所有不經(jīng)過大于k的節(jié)點的路徑中，肯定包括不大于k-1的，因為不大于k-1肯定也就不大于k，換個角度看，這些路徑也根本不經(jīng)過k；那么肯定還包括一些路徑是包括k的，這些路徑在第一次遇到k以前，可以認為是Rik(k-1)，隨后包括任意數(shù)量的k節(jié)點上的閉包Rkk(k-1)，隨后包括從k到j的一條已經(jīng)沒k了的路徑Rkj(k-1),綜上這種路徑表示為Rij(k)=Rij(k-1)+Rik(k-1)Rkk(k-1)*Rkj(k-1)。這也就是我們要找的計算任意k的公式。但是這樣帶入后得到的正則表達式很長，需要化簡。
最終，DFA對應的正則表達式是所有以初始狀態(tài)為i，終結狀態(tài)為j的表達式的并。
3.消除狀態(tài)簡化運算
對于任意一個不是初始狀態(tài)也不是終結狀態(tài)的狀態(tài)，都肯定有一定的前驅(qū)節(jié)點和后繼結點，要消去這個節(jié)點，只需要用適當?shù)恼齽t式在它的每個前驅(qū)和每個后繼之間做一個連接就行了。具體的方法在P66-67，很簡單。
4.正則表達式轉(zhuǎn)化為自動機（一般是ε-NFA）簡單地說，正則表達式有三種微元，分別是R+S型，RS型，R*型，這三種可以轉(zhuǎn)化成三種基本的NFA，任何正則表達式都能通過三種微元組合成。這三種NFA見課本P70-71
D. 正則語言性質(zhì)
1.正則語言具有封閉性，這和集合上的運算封閉性差不多，不多說了。能夠保證正則的運算包括：并，連接，閉包，交，補，差，反轉(zhuǎn)，同態(tài)和逆同態(tài)。同態(tài)就是把輸入串中每一個輸入都通過一個函數(shù)轉(zhuǎn)變成另一個串，該函數(shù)叫做串的同態(tài)。如果一個語言是正則的，針對其字母表的同態(tài)也是正則的，這是顯然的，因為就是做了個替換而已沒有本質(zhì)變化啊。
2.泵引理：為了驗證一個語言是不是正則的，我們需要使用泵引理，該引理稱，對于任意一個正則語言W，一定能把他分解成W=xyz，其中|xyz|>=n,y!=Φ,|xy|<=n,而且xy*z一定也屬于w。下面通過一個例子說明一下泵引理的用法。
證明{0(m)1(m) | m>=1}不是正則語言，其中0(m)表示0的m次我們假設這個語言是正則的，那么由于該語言的長度至少是2，所以n=2,將該語言分解成三部分，且|xy|<=2，只能令x=y=0,z=0(m-2)1(m),由于xy*z也屬于該正則語言，但是有任意個y的時候0的個數(shù)肯定和1的個數(shù)不等，也就是說這個語言不可能屬于{0(m)1(m)}得到矛盾，所以這個語言不是正則的。
3.測試正則語言是否為空：可以分別測試子正則語言是否為空
4.驗證正則語言中一對狀態(tài)是否等價：使用的填表算法是，橫軸為A.....(N-1),縱軸為中間狀態(tài)和接收狀態(tài)B.....N, 建一個三角形的表。如果A不是接收狀態(tài)但B是，那么{A,B}是一個可區(qū)分對，在其對應位置畫X，對于任意一對狀態(tài){M,N},如果某個輸入下M指向A，N指向B，那么這一對狀態(tài)可區(qū)分，可以根據(jù)這個特點遞歸直到無法推出更多可區(qū)分狀態(tài)對為止，那么無法推出的狀態(tài)對就是等價的。
5.自動機最小化：可以想象求出等價狀態(tài)就是為了消去他們……自動機的最小化要求首先把等價狀態(tài)作為一個狀態(tài)，然后把從初始狀態(tài)不可達的狀態(tài)除去，重構自動機即可。
E. 上下文無關文法和語言
相比前面的內(nèi)容，這一章更虛了……幾乎都是些不用腦子的東西
1. 上下文無關語言：可以認為是比正則語言更廣泛的一種語言，其“自然的遞歸記號”稱作文法。這些定義是什么意思無關緊要。簡單地說，文法就是描述語言的方法。而文法包括四個要素：符號的有窮集合（這些符號被稱作終結符號，類似于英語中的字母），變元的有窮集合（變元也被稱作非終結符或語法范疇，每一個變元代表了一類串，也就是一種語言），一個變元被稱作初始符號，以及一個規(guī)則（也稱作產(chǎn)生式）的集合。通俗地說，包括字母，語言集，一個基本語言和一個語法規(guī)則。文法縮寫式CFG，表達式是G=(V,T,P,S)。主要的應用是CFG描述語言并轉(zhuǎn)化為語法分析器，以及XML等標記語言語言結構。下面的例子可以迅速理解這些亂七八糟的東西
習題 定義一個CFG，它是一種表達式，但是運算符只有+和*，標識符必須由字母開頭，字母只有a和b，數(shù)字只有0和1。分析：該文法需要兩個變元，一個代表了整個表達式稱作E（也是一個初始符號），一個代表了其中的標識符稱作I，我們能得到下面的“文法”
E->I //表示表達式可以由標識符組成
E->E+E //表達式可以由兩個表達式+成
E->E*E //表達式可以由兩個表達式*成
E->(E)
I->a //表達式可以由a組成
I->b
I->Ia //表達式可以由I與a連接成
I->Ib
I->I0
I->I1
我們來看看a*(a+b00)是否屬于這個語言。E=>E*E=>I*E=>a*E=>a*(E)=>a*(E+E)=>a*(I+I)=>a*(a+I0)=>a*(a+I00)=>a*(a+b00)
可見屬于這個語言。
上面的文法可以表示為I=>a|b|Ia|Ib|I0|I1 ,E=>I|E+E|E*E|(E),上述驗證過程稱作推導。如果每次只替換最左邊的變元，就稱作最左推導，反之稱作最右推導。利于該文法在終結符號集合上產(chǎn)生的語言稱作上下文無關語言(CFL)。由初始符號得到的表達式稱作句型，比如E+E就是一個句型，和最左最右推導融合后還有左句型和右句型的概念。
?2. 語法分析樹：也就是推導的另一種表示法。對于一個文法G來說，語法分析樹滿足每個內(nèi)部節(jié)點的標號都是V的變元，每個葉節(jié)點可以是變元、終結符或者ε。一個節(jié)點的所有子節(jié)點按順序排列是這個節(jié)點對應變元的一個變換。推理和樹的互推非常淺顯，看兩個例子就明白了。
3. CFG和語言的歧義性：類似于1+2*3中先加還是先乘的問題，一個串可能有多個語法生成樹或者對應地，有多個最左推導或者最右推導，那么這個語言是有歧義的。某些文法無法消除歧義性，有些則沒有歧義性。一般的文法，消除歧義的方法就是使用優(yōu)先級和結合律，比如規(guī)定始終左結合或者右結合。對應地，無歧義文法只有唯一最左或最右推導。
強制優(yōu)先級是有效的消歧義方法，做法是引入不同的變元，其中因子是不能被相鄰運算符打斷的表達式，屬于因子的包括標識符本身和括號表達式。第二，項是不能被低級運算符打斷的表達式，第三就是普通的表達式。
由于這一部分很難語言描述，看題目比較容易明白，下面簡單說幾個習題的做法：?
習題 1.?證明如果一個串是括號匹配的，那么他能用文法B->BB|(B)|ε生成。證明：如果串長度為1，首先他當然是括號匹配的，設為T，可以用T->TT->Tε生成，假設成立。
??????????現(xiàn)在假設串長度為K成立，設串為TK，那么K+1時，要想串是括號匹配的，則他只能是用若干個匹配串組合即T(K+1)->T(M)T(N)或者組合后加括號，或者添加若干ε，都可以用該文法生成。歸納結束
2.證明S->aS|aSbS|ε這個文法是歧義的，即對串a(chǎn)ab有兩個語法分析樹，最左最右推導。思考在證明歧義性上面分析樹和最左右推導數(shù)量的等價性。
證明：最左推導：S->aS->aaSbS->aaεbS->aaεbε->aab,??S->aSbS->aaSbS->aaεbε->aab，最右推導和分析樹類似。
如果要制定一個沒有歧義的文法，因為原來文法的問題在于aab＝(aa)b或者a(ab)，所以需要強制結合性，這三個子表達式我們只能把結合性考慮在a、b都出現(xiàn)的aSbS上面，令b強制和前面的a結合就行了。做法是S->aTbS,?T->aTbT|ε
F. 下推自動機
?如同正則語言和有窮自動機等價，上下文無關語言和下推自動機(PDA)等價。下推自動機是附加了堆棧的ε-NFA。簡單地說，PDA有一個初始狀態(tài)和初始堆棧符號，之后他接受輸入改變狀態(tài)，根據(jù)當前輸入和狀態(tài)決定堆棧操作（壓棧或者彈出符號），最終到達終結狀態(tài)。公式P=(Q ,Σ, Γ, σ, Q0,Z0, F),分別對應狀態(tài)集合，輸入符號集合，堆棧字母表，轉(zhuǎn)移函數(shù)，初始狀態(tài)，初始堆棧符號和接收狀態(tài)集合。其中σ的自變量是狀態(tài)，輸入內(nèi)容和堆棧字母符號（棧頂），輸出則是新狀態(tài)和堆棧符號串的對的有限集合，即σ(q,a,X)={(q' , r), ....}
下推自動機的圖形表示和NFA類似，但是從狀態(tài)p到q的標號a,X/r表示σ(p,a,X)的輸出集合中包含了(q,r)對。
?PDA的每個狀態(tài)可以用三個變量描述，q代表一個狀態(tài)，w是剩余的串，r為堆棧內(nèi)容，(q,w,r)是一個PDA的瞬時描述(ID)。定義├符號是PDA從一個ID到另一個ID，用法如(q,aw,xβ)├(p,w,αβ),表示用剩余串的字符a代替了棧頂元素x，思考一下，如果x＝ε，這個式子代表了壓棧操作。
PDA有兩種接受方法，一種是到達終結狀態(tài)，稱作終結狀態(tài)方式接受， 一種是空棧方式接受。兩種構造方式下，PDA等價。那么自然，兩種方式可以相互轉(zhuǎn)化。從
終結狀態(tài)方式轉(zhuǎn)化到空棧，常用的方法是添加一個棧底標記符號X0,到達終結狀態(tài)的時候，添加一個轉(zhuǎn)移是從該狀態(tài)的ε輸入，彈出所有元素到空棧。例如σ(q, ε ,Y)={(q,ε)}
從文法到PDA，轉(zhuǎn)化方法是，對于每一個變元A，σ(q, ε, A)={(q,β)|A->β是文法的一個產(chǎn)生式}, 對于每一個終結符a，σ(q,a,a)={(q, ε)}
從PDA到文法，轉(zhuǎn)化方法是， 首先我們定義一個符號S為初始符號，以及所有形式為[pxq]的符號，pq是PDA中的狀態(tài)，X則是堆棧中的符號。
首先對于每一個狀態(tài)p，文法G都有產(chǎn)生式S->[q0Z0P], 也就是說初始符號能夠生成所有從初始ID出發(fā)到達空棧狀態(tài)的串w。其次，令 σ(q, a, X)包含一個輸出對(r,Y1Y2Y3.......YK)，那么G應該有一個產(chǎn)生式[qXrk]->a[rY1r1][r1Y2r2]... [r(k-1)Ykrk]，思考一下，這代表從狀態(tài)q到達狀態(tài)r(k)并從棧彈出X的一個方法是讀入a，之后讀入某些輸入，從棧中依次彈出 Y1Y2Y3.......YK，并轉(zhuǎn)過一些中間狀態(tài)r r1 r2.....r(k-1)，最后達到rk。而r1r2...rk代表狀態(tài)集的每一個有序序列，比如一個PDA有pq兩個狀態(tài)，那么按照pq和qp的順序要生成兩次。（我承認沒說明白＝ ＝）?
習題把文法S->0S1?|?A,?A->1A0?|?S|?ε轉(zhuǎn)化成空棧方式接受同樣語言的PDA，再把該PDA轉(zhuǎn)換成文法。首先σ(q,?ε?,?S)={(q,?0S1),?(q,?A)},?σ(q,?ε,?A)={(q,1A0),?(q,S),?(q,?ε?)}
然后σ(q,?0,?0)={(q,?ε)},?σ(q,?1,?1)={(q,ε)}
這就是我們構造出的PDA的轉(zhuǎn)移函數(shù)，對應PDA是P=(?{q},?{0,1},?{0,?1,?S,?A},?σ,?q,?S)
下面我們把這個PDA轉(zhuǎn)成文法
設置一個初始狀態(tài)S，那么S->[qSq],?而因為σ(q,?ε?,?S)={(q,?0S1),?(q,?A)}，[qSq]->ε[q0q][qSq][q1q]
[qSq]->ε[qAq],?[qAq]->[q1q][qAq][q0q],?[qAq]->[qSq],?[qAq]->[qεq]
[q0q]->0[qεq]=0,?[q1q]->1[qεq]=1;
簡化上面的式子，可以看到
[qSq]->0[qSq]1?|?[qAq]?,?[qAq]->1[qAq]0?|?[qSq]?|?ε
用A代替[qAq],?S代替[qSq]，可以得到題目中的文法
可以進一步感受到文法和PDA的等價性。
G.CFL的性質(zhì)
1.首先討論所謂CFG的范式，即任何不是ε的CFL都能用只有A->BC或者A->a形式的產(chǎn)生式的CFG產(chǎn)生，其中ABC是變元，a是終結符，這種形式稱作喬姆斯基范式。為了求出范式，我們要先給出一些定義。首先如果某個終結串w有X-*>w（-*>為任意多步數(shù)轉(zhuǎn)化），稱X是產(chǎn)生的。任何終結符都是產(chǎn)生的。此外，如果對于某個串 α和β有S-*>αXβ，稱X是可達的。
首先去掉無用符號，做法是去掉非產(chǎn)生符號和所有包含這些符號的產(chǎn)生式，之后去除非可達符號。而且他們產(chǎn)生的語言是相同的。在這個過程中有幾點注意事項：首先，文法G的終結符號集合T中的符號都是產(chǎn)生的，那么假定一個產(chǎn)生式A->α,而串α中的符號都是產(chǎn)生的，那么A也是產(chǎn)生的。通過這種方法得到的符號集也是這個文法中全部產(chǎn)生符號了。可見，尋找產(chǎn)生符號的過程是自底向上的，同樣，尋找可達符號是自頂向下的，而且得到的也是全部可達符號。然后去ε產(chǎn)生式。回想一下 ε，它在一個語言中不是必需的，如果一個語言有對應的CFG，那么他去掉ε后也有一個對應的不含ε產(chǎn)生式的CFG，如果CFG有一個產(chǎn)生式A->w,w中所有符號都可空或者w就是ε，那么A是可空符號。構造一個除ε產(chǎn)生式的CFG的方法是，對于每個產(chǎn)生式A->BCDEF....，假定其中有m個可空符號，那么新文法中，這些可空符號每個都有存在和不存在兩種可能，共有2m種組合，但是如果這些符號都可空，他們都不存在的話就是A->，這在新文法中不能出現(xiàn)，所以除去這種情況。這樣得到的文法是去ε產(chǎn)生式的。
對CFG???S->AB,A->aAA|ε,?B->bBB|ε
A,B都能直接生成ε，他們都是可空的，S生成符號都可空所以S可空。現(xiàn)在考慮生成式S->AB,A和B存在不存在共4中組合，但是AB都不存在是ε，要去掉，所以新文法中：S->AB|A|B,類似地，A->aAA|aA|a,?B->bBB|bB|b 之后去掉單位產(chǎn)生式，也就是A->B形式的產(chǎn)生式，其中AB必須都是變元。如果A-*>B，稱(A,B)為單位對。對于任意變元A, (A,A)是單位對，如果(A,B)是單位對，又有單位產(chǎn)生式B->C,那么(A,C)也是單位對。通過這個迭代可以得到所有單位對。之后對于每一 對單位對(A,B),如果有一個非單位產(chǎn)生式B->α，就把A->α放到新文法中，這樣得到的新聞法是不包含單位產(chǎn)生式的。首先去掉ε產(chǎn)生式，然后去單位產(chǎn)生式，最后去掉無用符號。這個順序可以保證結果是喬姆斯基范式(CNF)。但是對于CNF還有兩個要求，就是要用變元代替所有終結字符，如果有長度大于2的轉(zhuǎn)化，也要引入新的變元代替。例子將文法S->ASB|ε,?A->aAS|a,B->SbS|A|bb轉(zhuǎn)化為CNF
首先去ε產(chǎn)生式，只有S是可空的，那么檢查所有帶S的生成式并改正，為：
S->AB|ASB,?A->aA|aAS|a,B->Sb|bS|SbS|A|bb|b
然后去掉單位產(chǎn)生式，只有(B,A)是一個單位對，所以其它不變，?B?->?SbS?|?bS?|?Sb?|?b?|?aAS?|?aA?|?a?|?bb
最后檢查無用符號，結果是沒有
那么下面引入C->a,D->b
這樣還是有長度是3的生成式，引入新的變元代替他們，最后
?????S?->?AE?|?AB
?????A?->?CF?|?CA?|?a
?????B?->?SG?|?DS?|?SD?|?b?|?CF?|?CA?|?a?|?DD
?????C?->?a
?????D?->?b
?????E?->?SB
?????F?->?AS
?????G?->?DS
?2.下面給出CFL的泵引理證明某個語言不是上下文無關的：對于一個CFL L，存在常數(shù)n滿足：若L中的串z的長度>=n,就可以令z＝uvwxy, 且：|vwx|<=n, vx!=ε, 對于所有i>=0,uviwxiy也屬于L。
3. CFL在代入、并、連接、閉包、反轉(zhuǎn)和逆同態(tài)運算下都封閉，但是交補運算下不封閉，但CFL和正則語言的交依舊是CFL。
4.存在算法可以判斷CFG是否產(chǎn)生至少一個串，CYK算法可以判定一個串是否屬于一個給定的CFL，測試時間是O(n3) ,n是串長度。詳細算法看課本。有些問題是不可判定的，比如某個CFG是不是歧義的，是不是固有歧義的，兩個CFG交是否為空……等等。
?H. 圖靈機導引
首先要說明的是某些問題是不能判定的。為了證明一個問題是不是不可判定的，可以對他進行構造抽象，再特殊化得到一個實例，再對實例構造……最后對一個抽象實例判定，即所謂歸約技術。但是有個更方便簡單的計算機模型就是圖靈機。簡單地說（其實也就是這樣）圖靈機(TM)由一條劃分成單元的帶子和一個有窮控制單位組成。 單元上記錄有一個輸入符號，圖靈機的一步可以改變狀態(tài)或者在掃描的單元中寫符號或者移動帶頭。沒有輸入的單元用空格填充。空格不是輸入符號，但是是圖靈機的一個帶符號。圖靈機M＝(Q, Σ, Γ, σ ,q0,B,F),分別代表狀態(tài)的有窮集合，輸入符號集合，帶符號集合，轉(zhuǎn)移函數(shù)，初始狀態(tài)，空格和終結狀態(tài)。其中σ(q,X)=(p,Y,D)，表示某個狀態(tài)q下正在掃描X，轉(zhuǎn)移到狀態(tài)p，在X的位置上寫下Y，并向左或右移(D=L或R).同樣圖靈機也有ID，是用X1X2...Xi-1qXiXi+1...Xn表示的，其中q是TM的當前狀態(tài)，而帶頭正在掃描第i個符號(Xi)，剩下的內(nèi)容表示Xi左邊和右邊空格之內(nèi)的部分。圖靈機的轉(zhuǎn)移圖上弧標記形如0/0->，表示在此狀態(tài)下將0改寫成0，并右移。
同樣圖靈機也和一種語言等價，即遞歸可枚舉語言(RE)。此外，如果圖靈機在某狀態(tài)下掃描到一個未定義的輸入 ，則停機。為了用圖靈機生成字符串，比較有用的技巧包括用狀態(tài)存儲，多道和子程序。此外還有多帶圖靈機，并可以證明它和單帶圖靈機等價。類似DFA和NFA的關系，也存在非確定圖靈機(NTM)，同樣NTM和TM也能相互轉(zhuǎn)化。對TM稍作改造可以形成半無窮帶TM、多堆棧機器和計數(shù)器機器。此外計算機和圖靈機可以互相模擬。
?I. 不可判定性
?圖靈機接受RE，對于一個輸入語言，TM有兩種行為。一種是經(jīng)過狀態(tài)轉(zhuǎn)變最終停機，不管是接收狀態(tài)的停機還是不接受狀態(tài)停機，這種情形稱作有算法。而另一種就是陷入死循環(huán)，這種問題稱作不可判定性問題。首先，對角化語言非RE：簡單地說，將一個圖靈機進行編碼。圖靈機的狀態(tài)和符號都可以枚舉成數(shù)字，方向有兩個，轉(zhuǎn)移函數(shù)也就因此可以編碼，從而圖靈機可以編碼成二進制串。而這些二進制串也可以枚舉。方法是在串前面加個1然后轉(zhuǎn)十進制，比如串0編碼是第2個串。之后建表將對角線取補得到的語言可以確定不被任何圖靈機接受。對角化語言Ld是非遞歸可枚舉的。
從前面可以看到，RE也非為遞歸語言和非遞歸語言。遞歸語言的補也遞歸，同樣，語言L和他的補都是RE，那么L遞歸。
對于每個TM M和它接受的語言w可以組成有序?qū)?M,w),有序?qū)Φ募袭a(chǎn)生的語言即所謂通用語言Lu，而Lu一定有接受它的圖靈機，即通用圖靈機。盡管如此，Lu不可判定。
?
-------------------------------------
到此自動機的總結完成，雖然說不可判定性和難解問題還有一些沒有說，但是貌似考試大綱不包括這些內(nèi)容。下面為了方便有一個縮略詞表：
?CFG 上下文無關文法 CFL 上下文無關語言 CNF 合取范式 DFA有窮狀態(tài)自動機 DPDA 確定型下推自動機 ID 瞬時描述 NFA 非確定型有窮自動機 PDA 下推自動機 TM 圖靈機 RE 遞歸可枚舉語言 NTM 非確定圖靈機
轉(zhuǎn)載于:https://www.cnblogs.com/superx/archive/2010/12/13/1868673.html
總結
以上是生活随笔為你收集整理的自动机理论、形式语言和计算导论提纲的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 前端一些面试问题3
- 下一篇： Oracle 中间件云服务器系统 Exa