1、精選優(yōu)質(zhì)文檔-傾情為你奉上計算機(jī)組成原理與結(jié)構(gòu)期末論文有限自動機(jī)的原理及示例 學(xué)院： 專業(yè)： 姓名： 學(xué)號： 有限自動機(jī)的原理及示例本文將介紹幾種重要有限自動機(jī)的基本原理，并通過例子說明它們的運(yùn)行過程。一 語言的基本概念一張字母表是一個非空有限集合，字母表中的每個元素稱為中的一個字母，也稱符號、終止符或者字符。中有限個字符有序地排列起來就稱為上的一個字符串，稱為它的長度。其中有一個特殊的串，它的長度為零。若和都是字母表，則它們的乘積定義為，特別地，令若，且則稱是的子串。 字母表上的一種語言是的一個子集。二 有限狀態(tài)自動機(jī)的原理和運(yùn)算實例1.基本原理一個有限狀態(tài)自動機(jī)的物理模型通常包括兩部分：（

2、1）一個輸入存儲帶，帶被分解為多個單元，每個單元存放一個輸入符號（字母表上的符號），整個輸入串從帶的左端點(diǎn)開始存放，而帶的右端可以無限擴(kuò)充。 （2）一個有限狀態(tài)控制器（FSC）,該控制器的狀態(tài)只能是有限個；FSC通過一個讀頭和帶上單元發(fā)生耦合，可以讀出當(dāng)前帶上單元的字符。初始時，讀頭對應(yīng)帶的最左單元，每讀出一個字符，讀頭向右移動一個單元。 有限狀態(tài)自動機(jī)的一個動作為：讀頭讀出帶上當(dāng)前單元的字符；FSC根據(jù)當(dāng)前FSC的狀態(tài)和讀出的字符，改變FSC的狀態(tài)；并將讀頭右移一個單元。接著給出有限狀態(tài)自動機(jī)的數(shù)學(xué)模型。字母表上的一個有限狀態(tài)自動機(jī)(FSAM)是一個五元組其中，i)是一個有限狀態(tài)的集合；ii

3、)是字母表，它是輸入帶上的字符的集合； iii)是開始狀態(tài)； iv)是接收狀態(tài)（終止?fàn)顟B(tài)）集合； v)是狀態(tài)轉(zhuǎn)換函數(shù)，表示自動機(jī)在狀態(tài)時，掃描字符后到達(dá)狀態(tài)。對于有限狀態(tài)自動機(jī)，給定字母表上的串；初始時，自動機(jī)處于開始狀態(tài)；從左到右逐個字符地掃描串；在的作用下，自動機(jī)處于狀態(tài)，在的作用下，自動機(jī)處于狀態(tài)，當(dāng)將串掃描結(jié)束后，若自動機(jī)處于某一個接收狀態(tài)，則稱有限狀態(tài)自動機(jī)能夠接收（識別）串。對于自動機(jī)而言，從開始狀態(tài)開始，在掃描串的過程中，狀態(tài)逐個地變化，直到某個接收狀態(tài)，把狀態(tài)的變化過程稱為自動機(jī)的一條路徑，而這條路徑上所標(biāo)記的字符的連接，就是自動機(jī)所識別的串。有時為了表述方便，也采用如下定義的

4、擴(kuò)展的狀態(tài)轉(zhuǎn)換函數(shù)即自動機(jī)在一個狀態(tài)時，掃描串后到達(dá)唯一確定的狀態(tài)；換句話說，如果是一個字母，是一個字符串，那么并且對串，. 用表示被接收的語言，它在字母表上，即，則. 若語言對某個自動機(jī)有，則稱語言為一個有限狀態(tài)語言。 有限狀態(tài)自動機(jī)的瞬時描述是一個二元組，其中是輸入帶上還沒有被掃描到的字符串，F(xiàn)SC的當(dāng)前狀態(tài)為，讀頭將馬上掃描串的左邊第一個符號。有限狀態(tài)自動機(jī)的初始格局為，接收格局為，其中是初始狀態(tài)，是某個接收狀態(tài)。 有限狀態(tài)自動機(jī)在下面兩種情形下停機(jī)：（1） 輸入串掃描結(jié)束時；（2） 有限狀態(tài)自動機(jī)的當(dāng)前格局為，而自動機(jī)沒有對應(yīng)的函數(shù)的定義，即沒有定義。在這種情形，可以補(bǔ)充定義一個特殊的

5、狀態(tài)：陷阱狀態(tài)，即。對于陷阱狀態(tài)，對任何字母，定義.2.兩個例子例2.1 我們將構(gòu)造一個有限狀態(tài)自動機(jī)，它能識別上的語言.分析：語言的特點(diǎn)是語言中的每個串都包含連續(xù)的3個0，故FSC的狀態(tài)及其意義如下：（1）：有限狀態(tài)自動機(jī)的開始狀態(tài)，也是重新尋找子串000時的狀態(tài)；（2）：有限狀態(tài)自動機(jī)讀到第一個0，有可能是子串000的第一個0；（3）：有限狀態(tài)自動機(jī)在后又讀到一個0；（4）：有限狀態(tài)自動機(jī)在后又讀到一個0，這是唯一的接收狀態(tài)。因此，狀態(tài)轉(zhuǎn)移函數(shù)為接收狀態(tài)為.例2.2 構(gòu)造有限狀態(tài)自動機(jī)，識別上的語言，該語言的每個字符串看成二進(jìn)制數(shù)時，代表的數(shù)字能整除3.分析：使用3個狀態(tài)分別代表已經(jīng)讀入的

6、數(shù)除以3的得到不同余數(shù)的等價類：（1）：已經(jīng)讀入的數(shù)除以3，余數(shù)為0的輸入串的等價類；（2）：已經(jīng)讀入的數(shù)除以3，余數(shù)為1的輸入串的等價類；（3）：已經(jīng)讀入的數(shù)除以3，余數(shù)為2的輸入串的等價類；因為不能接收空串，所以還需要一個開始狀態(tài)。設(shè)是當(dāng)前讀入的輸入串，則（1）：在開始狀態(tài)讀入0時，有，進(jìn)入狀態(tài)；讀入1時，有，進(jìn)入狀態(tài)。（2）：能引導(dǎo)自動機(jī)到達(dá)此狀態(tài)的是3的倍數(shù)，因此。 a)在此狀態(tài)讀入0，引導(dǎo)自動機(jī)到達(dá)下一狀態(tài)的輸入串為，則，這表明也屬于對應(yīng)的等價類。所以自動機(jī)在狀態(tài)讀入0應(yīng)該繼續(xù)保持狀態(tài)。 b)在此狀態(tài)讀入1，引導(dǎo)自動機(jī)，到達(dá)下一狀態(tài)的輸入串為，則，這表明屬于對應(yīng)的等價類。所以自動機(jī)在

7、狀態(tài)讀入1應(yīng)該進(jìn)入狀態(tài)。(3): 能引導(dǎo)自動機(jī)到達(dá)此狀態(tài)的滿足。a)在此狀態(tài)讀入0，引導(dǎo)自動機(jī)到達(dá)下一狀態(tài)的輸入串為，則，這表明屬于對應(yīng)的等價類。所以自動機(jī)在狀態(tài)讀入0進(jìn)入狀態(tài)。b)在此狀態(tài)讀入1，引導(dǎo)自動機(jī)到達(dá)下一狀態(tài)的輸入串為，則，這表明屬于對應(yīng)的等價類。所以自動機(jī)在狀態(tài)讀入1進(jìn)入狀態(tài)。（4）：能引導(dǎo)自動機(jī)到達(dá)此狀態(tài)的滿足。 a)在此狀態(tài)讀入0，引導(dǎo)自動機(jī)到達(dá)下一狀態(tài)的輸入串為，則，這表明屬于對應(yīng)的等價類。所以自動機(jī)在狀態(tài)讀入0進(jìn)入狀態(tài)。b)在此狀態(tài)讀入1，引導(dǎo)自動機(jī)到達(dá)下一狀態(tài)的輸入串為，則，這表明屬于對應(yīng)的等價類。所以自動機(jī)在狀態(tài)讀入1繼續(xù)保持狀態(tài)。因此狀態(tài)轉(zhuǎn)換函數(shù)為接收狀態(tài)為。三 帶

8、輸出的有限狀態(tài)自動機(jī)1. Moore機(jī)的原理Moore機(jī)的數(shù)學(xué)模型是一個六元組其中 1）的含義同有限狀態(tài)自動機(jī)。 2）是輸出字母表。 3）是輸出函數(shù)。對于，表示Moore機(jī)在狀態(tài)時輸出。 Moore機(jī)在讀入輸入串的過程中，狀態(tài)不斷發(fā)生改變，并且在每個狀態(tài)上都有輸出。 對于輸入串序列，Moore機(jī)的輸出序列為這里因此，如果輸入串的長度為，那么Moore機(jī)的輸出串的長度為。2. Moore機(jī)的運(yùn)算示例例3.1 構(gòu)造一個Moore機(jī)，若將輸入串當(dāng)作一個二進(jìn)制數(shù)，則在讀入串的過程中，希望輸出已經(jīng)讀過的子串模3的余數(shù)。分析：因為模3的余數(shù)只有0、1和2，所以輸出字母表，并設(shè)3個狀態(tài)（1）：已經(jīng)讀入的數(shù)除

9、以3，余數(shù)為0的輸入串的等價類；（2）：已經(jīng)讀入的數(shù)除以3，余數(shù)為1的輸入串的等價類；（3）：已經(jīng)讀入的數(shù)除以3，余數(shù)為2的輸入串的等價類；像例2.2那樣，狀態(tài)轉(zhuǎn)換函數(shù)為根據(jù)狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果，輸出函數(shù)為 例如當(dāng)輸入空串時，輸出余數(shù)為0；當(dāng)輸入1010時，狀態(tài)變換的序列為對應(yīng)的輸出序列為01221。3. Mealy機(jī)的原理Mealy機(jī)的數(shù)學(xué)模型是一個六元組其中1）的含義同有限狀態(tài)自動機(jī)。 2）是輸出字母表。 3）是輸出函數(shù)。對于，表示Moore機(jī)在狀態(tài)，讀入字母時，輸出。 Mealy機(jī)在讀入串的過程中，狀態(tài)不斷發(fā)生改變，并且在每個狀態(tài)上，讀入某個字母時，Mealy機(jī)都有輸出。 對于輸入串序列，Mealy機(jī)的輸出序列為這里因此，如果輸入串的長度為，那么Moore機(jī)的輸出串的長度也為。4. Mealy機(jī)的運(yùn)算示例例3.2 構(gòu)造一個只有兩個輸出符號的Mealy機(jī)，對于上的語言，當(dāng)讀過的輸入串屬于時，Mealy機(jī)輸出，表示接收；當(dāng)讀過的輸入串不屬于時，Mealy機(jī)輸出，表示拒絕。分析：定義3個狀態(tài)（1）：開始狀態(tài)。（2）：自動機(jī)讀入的字符是0。（3）：自動機(jī)讀入的字符是1。那么（1）：若即將讀入0，則自動機(jī)進(jìn)入狀態(tài)，同時輸出；若即將讀入1，則自動機(jī)進(jìn)入狀態(tài)，同時輸出。（2）：若即將讀入0，則自動機(jī)保持狀態(tài)，同時輸出；若即將讀入1，則自動機(jī)進(jìn)入狀態(tài)，同