計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)第二章

1、2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)1第二章 有限自動機(jī)2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)22. 1 有限自動機(jī)的定義與構(gòu)造有限自動機(jī)的定義與構(gòu)造 有限自動機(jī)（Finite AutomataFA）或稱為有窮狀態(tài)的機(jī)器，由一個(gè)有限的內(nèi)部狀態(tài)集和一組控制規(guī)則組成。 在計(jì)算機(jī)科學(xué)中，可以找到許多有限狀態(tài)系統(tǒng)的例子，如計(jì)算機(jī)本身也可以是認(rèn)為是一個(gè)有限狀態(tài)系統(tǒng)。 有限自動機(jī)與正規(guī)文法和正規(guī)式有著非常密切的關(guān)系，它們的描述能力是相同的。 2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)3例例2.1 構(gòu)造一個(gè)有限自動機(jī)M0，它能識別出除以3余2的二進(jìn)制數(shù)。 解：用V3(x)來表示二進(jìn)制數(shù)x除以3的余數(shù)，例

2、如，V3 (100)1, V3 (1011)2，設(shè)輸入符號串為wa1a2an，其中ai0, 1，0in。顯然，對于每一個(gè)i，0in，自動機(jī)讀入符號串a(chǎn)1a2ai后，二進(jìn)制數(shù)a1a2ai除以3的余數(shù)V3(a1a2ai)必然為0、1、2之一，不可能有其它情況。因此可知，在自動機(jī)M0中只需要采用三個(gè)狀態(tài)來分別表示上述的三種情況即可。令自動機(jī)M0中有狀態(tài)q0、狀態(tài)q1和狀態(tài)q2分別表示余數(shù)為0、1和2的情況。 2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)4狀態(tài)之間的轉(zhuǎn)換狀態(tài)之間的轉(zhuǎn)換 當(dāng)M0讀完符號串a(chǎn)1a2ai后又讀到符號ai+1時(shí)，新符號串a(chǎn)1a2ai ai+1除3的余數(shù)與原符號串a(chǎn)1a2ai除3的余

3、數(shù)之間顯然有：V3(a1a2ai ai+1) 2*V3(a1a2ai) + ai+1(mod 3) 101010圖2. 1 有限自動機(jī)M0q0q1q22021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)5自動機(jī)的抽象模型 可以將有限自動機(jī)抽象地描述成如圖2.2所示的模型，該模型由一條無窮長度的輸入帶、一個(gè)讀頭和一個(gè)有限控制器組成。 圖2.2 有限自動機(jī)讀頭有限狀態(tài)控制器0 1 0 1 1 0 輸入帶2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)6確定的有限自動機(jī)定義定義2. 1 一個(gè)確定有限自動機(jī)(DFA)M是一個(gè)五元組 M = (S, , f, s0, Z)其中： 是有窮字母表,它的每一個(gè)元素稱為一個(gè)輸入符號

4、； S是有限狀態(tài)集，它的每一個(gè)元素稱為一個(gè)狀態(tài)； f是轉(zhuǎn)換函數(shù)，是從SS上的一個(gè)單值映射，即f(p, a)q，q稱為p的后繼狀態(tài)； s0 S是一個(gè)唯一的初始狀態(tài)唯一的初始狀態(tài)； Z S是一個(gè)終止?fàn)顟B(tài)集終止?fàn)顟B(tài)集。對于一個(gè)給定的屬于該自動機(jī)的狀態(tài)和一個(gè)屬于該自動機(jī)字母表對于一個(gè)給定的屬于該自動機(jī)的狀態(tài)和一個(gè)屬于該自動機(jī)字母表的字符，它都能根據(jù)的字符，它都能根據(jù)事先給定的轉(zhuǎn)移函數(shù)轉(zhuǎn)移到下一個(gè)事先給定的轉(zhuǎn)移函數(shù)轉(zhuǎn)移到下一個(gè)唯一確定的唯一確定的狀態(tài)（這個(gè)狀態(tài)可能是先前那個(gè)狀態(tài)）。狀態(tài)（這個(gè)狀態(tài)可能是先前那個(gè)狀態(tài)）。定義定義2. 2 DFA M所接受的符號串的集合稱為DFA M所接受的語言，記為L(M)

5、，即： L(M)w | f(s0, w)Z，w* 2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)7不確定的有限自動機(jī)(NFA)定義定義2. 3 一個(gè)不確定有限自動機(jī)M是一個(gè)五元組 M( S, , f, S0, Z)其中： 是有窮字母表,每一個(gè)元素稱為一個(gè)輸入符號； S是有限狀態(tài)集，每一個(gè)元素稱為一個(gè)狀態(tài)； f是轉(zhuǎn)換函數(shù): S (S)上的映射(S)是S的冪集)，即f(p,a)q1,.,qk，表示當(dāng)前的狀態(tài)為p，輸入符號為a時(shí)，則轉(zhuǎn)換到的狀態(tài)是一個(gè)狀態(tài)集； S0 S是初始狀態(tài)集初始狀態(tài)集； Z S是終止?fàn)顟B(tài)集終止?fàn)顟B(tài)集 。對于一個(gè)給定的屬于該自動機(jī)的狀態(tài)和一個(gè)屬于該自動機(jī)字母表對于一個(gè)給定的屬于該自動機(jī)

6、的狀態(tài)和一個(gè)屬于該自動機(jī)字母表的字符，的字符，它將根據(jù)事先給定的轉(zhuǎn)移函數(shù)轉(zhuǎn)移到下一個(gè)它將根據(jù)事先給定的轉(zhuǎn)移函數(shù)轉(zhuǎn)移到下一個(gè)不確定的不確定的狀態(tài)（因?yàn)檗D(zhuǎn)換到的狀狀態(tài)（因?yàn)檗D(zhuǎn)換到的狀態(tài)是一個(gè)狀態(tài)集）。態(tài)是一個(gè)狀態(tài)集）。2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)8DFA與NFA的比較 DFA的轉(zhuǎn)換函數(shù)是從S到S上的一個(gè)單值映射。 NFA的轉(zhuǎn)換函數(shù)是從S到(S) (S的冪集)的映射，而不是到S的映射，即一個(gè)狀態(tài)可轉(zhuǎn)換到的后繼狀態(tài)是一個(gè)狀態(tài)集合(可能是空集)，而不是單個(gè)狀態(tài)。 NFA有一個(gè)初態(tài)集, DFA的初態(tài)是唯一的。 DFA和NFA都正好識別正規(guī)集。 它們之間存在著時(shí)空權(quán)衡問題, DFA識別速度快，占

7、用空間大，NFA識別速度慢，占用空間小。 2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)9非確定有限自動機(jī)的推廣 將具有動作的非確定有限自動機(jī)定義為五元組( S, , f, S0 , Z)，其中除轉(zhuǎn)移函數(shù)f外的分量的定義如同定義2. 3，但轉(zhuǎn)移函數(shù)f是如下映射：S () (S) f(q, )q。 若NFA的某些狀態(tài)既是初態(tài)又是終態(tài)，則空字可為該NFA M所接受。 具有動作的NFA并不增加NFA接受語言的能力。 2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)10 定理定理2. 1 對任何一個(gè)具有動作的NFA M ，一定存在一個(gè)不具有-轉(zhuǎn)移的NFA M，使得L(M)L(M)。 其證明的基本思想是去掉弧。 DF

8、A可視為NFA的一個(gè)特例，其中： (1) 沒有一個(gè)狀態(tài)有轉(zhuǎn)換； (2) 對每一個(gè)狀態(tài)s和輸入符號a，最多只有一條標(biāo)記為a的弧離開。 對于任何兩個(gè)有限自動機(jī)對于任何兩個(gè)有限自動機(jī)M和和M，如果，如果L(M)L(M)，則稱，則稱M和和M是等價(jià)的是等價(jià)的。 2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)112.4 NFA的確定化如果把狀態(tài)子集看作是整體，即把一個(gè)狀態(tài)子集看作是一個(gè)（擴(kuò)展）狀態(tài)，那么NFA的不確定性就不存在了（子集構(gòu)造法子集構(gòu)造法）。定理定理2.2 設(shè)L(M)為一個(gè)由NFA M接受的集合，則存在一個(gè)接受L(M)的DFA M 。 圖2. 9 與圖2.5中NFA 等價(jià)的DFAbabbbabaaa

9、0 0 ，1 0 ，2 0 ，3ab0, 1, 30, 2, 3將狀態(tài)子集當(dāng)作一個(gè)（擴(kuò)展）狀態(tài)看待2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)122.5 DFA的最小化 由于NFA的確定化算法中沒有考慮到DFA中有些狀態(tài)是等價(jià)的，故得到的DFA的狀態(tài)數(shù)并不一定是最少的。定義定義2.6 一個(gè)狀態(tài)是DFA M的無用的,如果從M的初態(tài)出發(fā),任何輸入串都不能到達(dá)該狀態(tài).定義定義2.7 DFA M的兩個(gè)狀態(tài)s，t說是不可區(qū)別的，若對于輸入字母表上的任何符號串w，DFA M分別從s和t開始，讀完w之后，都同樣終止于終態(tài)或者非終態(tài)。 2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)13 終態(tài)與非終態(tài)是可區(qū)別的（令w=

10、）。 關(guān)系“不可區(qū)別”是一種等價(jià)關(guān)系。定義定義2.8 如果兩個(gè)狀態(tài)是不可區(qū)別的，則稱它們是等價(jià)的。定義定義2.9 DFA M的狀態(tài)最小化，是指構(gòu)造一個(gè)等價(jià)的DFA M,使得M是所有等價(jià)于M的DFA中狀態(tài)數(shù)目最少的,稱M為最簡DFA 。 DFA M是最簡DFA，須滿足如下兩個(gè)條件： (1) 沒有多余狀態(tài)； (2) 它的所有狀態(tài)都是可區(qū)別的，即沒有兩個(gè)狀態(tài)是等價(jià)的。 2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)14DFA可表示為RE 定理定理2.4：如果L被一個(gè)確定的有限自動機(jī)接受，則L可以用一個(gè)正規(guī)表達(dá)式來表示。 證明：令L被確定的有限自動機(jī)M所接受。設(shè) M = (q1, q2, , qn, , ,

11、 q1, F)。 令Rikj表示所有這樣的符號串x的集合，x滿足條件(qi, x) = qj，并且對x的任何不同于x或的前綴y，若(qi, y) = qs，則s k。 注意到L(M) = qjF R1nj。若對任意i, j, k，Rikj均可表示為正規(guī)式，則L(M)亦可表示為正規(guī)式。2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)15DFA可表示為RE 遞歸地定義Rikj 為：a | (qi, a) = qj i ja | (qi, a) = qj i = jRi0j =Rikj = Rik1j Rik1k (Rkk1k)*Rkk1jqiqjqkRik1jRik1k Rkk1kRkk1j 歸納基礎(chǔ)(k

12、 = 0)：顯然Ri0j可表示正規(guī)式ri0j 。 假設(shè)對i, j, k， Rikj均可表示為正規(guī)式rikj，則 Rik+1j亦可表示為正規(guī)式rik+1j，rik+1j = rikj rikk+1 (rk+1kk+1)*rk+1kj。 由數(shù)學(xué)歸納法可知?dú)w納假設(shè)成立。 2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)16雙向有限自動機(jī)雙向有限自動機(jī) 雙向確定有限自動機(jī)（2DFA）是五元組 M = (Q，q0，F(xiàn))， 其中Q，q0，F(xiàn)的定義和DFA一樣，而是從Q到Q L，R 的映射。 若(q，a)=(p，L)，則2DFA在狀態(tài)q掃描輸入符a后進(jìn)入狀態(tài)p并將磁頭左移一個(gè)單元。若(q，a)=(p，R)，則2DF

13、A進(jìn)入狀態(tài)p并將磁頭右移一個(gè)單元。2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)172DFA的瞬時(shí)描述 M的一個(gè)瞬時(shí)描述是*Q*中的一個(gè)符號串，瞬時(shí)描述wqx，其中w和x屬于*，而q屬于Q，表示了如下的事實(shí)： 1、wx為輸入符號串； 2、q是目前的狀態(tài)； 3、輸入磁頭正在掃描x的第一個(gè)符號。 如果x = ，則輸入磁頭已經(jīng)離開了輸入符號串的右端。2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)182DFA的瞬時(shí)描述的演變 定義關(guān)系M，或（當(dāng)M是已知時(shí)），為： （1）a1a2ai1qaiana1a2ai1ai p ai+1an，當(dāng)(q, ai) = (p, R)，和 （2）a1a2ai2 ai1qaian a1

14、a2ai2 p ai1 aian，當(dāng)(q, ai) = (p, L)，并且i 1。 (2) 中條件i 1防止使磁頭從磁帶左端移出的動作。注意，當(dāng)i = n + 1時(shí)不可有任何移動（因磁頭已移出右端）。令*為的自反閉包，即有I* I；或I2，, Ik-1，使得I1 I2 Ik，則I1* Ik。2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)192DFA及其瞬時(shí)演變 右圖是一個(gè)2DFA。 q0101001 1q101001 10q11001 1q201001 10q01001 101q1001 1010q101 10100q11 1010q201 10100q01 101001q1 0 1 q0 (q0,

15、 R) (q1, R) q1 (q1, R) (q2, L) q2 (q0, R) (q2, L)狀態(tài)狀態(tài)輸入輸入2DFA M1 0 1 0 0 1q0q1q1q2q0q1q1q1q2q0q1左表中2DFA M動作的圖示 下表是其閱讀輸入101001的演變：2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)20將2DFA看成單向運(yùn)動 如果我們把2DFA在每兩個(gè)單元之間的邊界下反復(fù)通過的狀態(tài)看作一個(gè)整體，不妨把這些通過的狀態(tài)序列稱為通過序列通過序列。 1 0 1 0 0 1從通過序列看2DFA的運(yùn)動q0q1q1q2q0q1q1q1q2q0q1 從通過序列的角度看，則是從前一個(gè)通過序列到達(dá)后一個(gè)通過序列的單

16、向運(yùn)動。 2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)212DFADFA的兩個(gè)問題 將2DFA轉(zhuǎn)換為單向運(yùn)動需要解決兩個(gè)問題： 首先，能否用有限的狀態(tài)來模擬通過序列。 其次，怎樣來確定通過序列之間的轉(zhuǎn)換。2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)22有效通過序列是有限的 只需考慮被2DFA M所接受的符號串的通過序列，稱之為有效通過序列有效通過序列。 有效通過序列是有限的。因?yàn)椋?1、若M接受該輸入串，則其通過序列在磁頭移動的同方向上不能有重復(fù)狀態(tài)，否則， M因其確定性而將陷入循環(huán)而永遠(yuǎn)不會移出輸入帶右端。設(shè)M有n個(gè)狀態(tài)，則有效通過序列長度不能超過2n。 2、磁頭首次通過該邊界時(shí)必是向右，隨后的通過

17、必是與前次反向，末次通過必是向右。故有效通過序列的長度都為奇數(shù)2n1。 2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)23有效通過序列之間的轉(zhuǎn)換 設(shè)含符號a的單元的左、右邊界的通過序列q = q1q2qk和p = p1p2pl是相容的。aq1q2qkp1p2pl 若M是向右移動進(jìn)入通過序列q和p，即(q1, a) = (p1, R)，則稱q右匹配p。 若M是向左移動進(jìn)入通過序列p和q，即(p1, a) = (q1, L)，則稱q左匹配p。aq1q2qkp1p2pl2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)24有效通過序列之間轉(zhuǎn)換的構(gòu)造 (a)、若q3qk右匹配p1pl，且(q1, a) = (q2,

18、L)，則q1q2q3qk右匹配p1pl。 (b)、若q2 qk左匹配p2pl，且(q1, a) = (p1, R)，則q1q2qk右匹配p1p2pl。q3qkq1q2ap1pl(a)：q1p1(b)：ap2plq2qk2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)25有效通過序列之間轉(zhuǎn)換的構(gòu)造 (c)、若q1qk左匹配p3pl，且(p1, a) = (p2, R)，則q1q2q3qk左匹配p1pl。 (d)、若q2 qk右匹配p2pl，且(p1, a) = (q1, L)，則q1q2qk左匹配p1p2pl。q1qkp1p2ap3pl(c)：q1p1(d)：ap2plq2qk2021-12-28計(jì)算機(jī)

19、科學(xué)的數(shù)學(xué)基礎(chǔ)262DFA接受的仍然是正規(guī)集 定理定理2.5：如果L被一雙向確定有限自動機(jī)接受，則L是一正規(guī)集。 證明：設(shè)M = (Q, , , q0, F)為2DFA?，F(xiàn)構(gòu)造一個(gè)NFA M = (Q, , , q0, F)，其中 (1) Q由M的所有有效通過序列組成； (2) q0是只由q0構(gòu)成的通過序列； (3) F是僅含M的一個(gè)終態(tài)的通過序列的集合； (4)(q, a)=p | 對符號a， q右匹配p。 用數(shù)學(xué)歸納法容易證明L(M) = L(M)。2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)27具有輸出的有限自動機(jī) 有限自動機(jī)的輸出有兩個(gè)不同的方法： 一種稱為Moore機(jī)器：M = (Q, , , , , q0)，其中Q，和q0和DFA中是一樣的，是輸出字母表，而是從Q到的一個(gè)映射，即給出與每個(gè)狀態(tài)相聯(lián)系的輸出。 另一種稱為Mealy機(jī)器： M = (Q, , , , , q0)，其中除了是從Q到的映射外，其余的都和Moore機(jī)器中一樣。 由狀態(tài)輸出由轉(zhuǎn)換輸出2021-12-28計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)28Moore機(jī)與Mealy機(jī)輸出長度差一 Moore