




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、精選優(yōu)質(zhì)文檔-傾情為你奉上計(jì)算機(jī)組成原理與結(jié)構(gòu)期末論文有限自動(dòng)機(jī)的原理及示例 學(xué)院: 專業(yè): 姓名: 學(xué)號(hào): 有限自動(dòng)機(jī)的原理及示例本文將介紹幾種重要有限自動(dòng)機(jī)的基本原理,并通過例子說明它們的運(yùn)行過程。一 語言的基本概念一張字母表是一個(gè)非空有限集合,字母表中的每個(gè)元素稱為中的一個(gè)字母,也稱符號(hào)、終止符或者字符。中有限個(gè)字符有序地排列起來就稱為上的一個(gè)字符串,稱為它的長度。其中有一個(gè)特殊的串,它的長度為零。若和都是字母表,則它們的乘積定義為,特別地,令若,且則稱是的子串。 字母表上的一種語言是的一個(gè)子集。二 有限狀態(tài)自動(dòng)機(jī)的原理和運(yùn)算實(shí)例1.基本原理一個(gè)有限狀態(tài)自動(dòng)機(jī)的物理模型通常包括兩部分:(
2、1)一個(gè)輸入存儲(chǔ)帶,帶被分解為多個(gè)單元,每個(gè)單元存放一個(gè)輸入符號(hào)(字母表上的符號(hào)),整個(gè)輸入串從帶的左端點(diǎn)開始存放,而帶的右端可以無限擴(kuò)充。 (2)一個(gè)有限狀態(tài)控制器(FSC),該控制器的狀態(tài)只能是有限個(gè);FSC通過一個(gè)讀頭和帶上單元發(fā)生耦合,可以讀出當(dāng)前帶上單元的字符。初始時(shí),讀頭對(duì)應(yīng)帶的最左單元,每讀出一個(gè)字符,讀頭向右移動(dòng)一個(gè)單元。 有限狀態(tài)自動(dòng)機(jī)的一個(gè)動(dòng)作為:讀頭讀出帶上當(dāng)前單元的字符;FSC根據(jù)當(dāng)前FSC的狀態(tài)和讀出的字符,改變FSC的狀態(tài);并將讀頭右移一個(gè)單元。接著給出有限狀態(tài)自動(dòng)機(jī)的數(shù)學(xué)模型。字母表上的一個(gè)有限狀態(tài)自動(dòng)機(jī)(FSAM)是一個(gè)五元組其中,i)是一個(gè)有限狀態(tài)的集合;ii
3、)是字母表,它是輸入帶上的字符的集合; iii)是開始狀態(tài); iv)是接收狀態(tài)(終止?fàn)顟B(tài))集合; v)是狀態(tài)轉(zhuǎn)換函數(shù),表示自動(dòng)機(jī)在狀態(tài)時(shí),掃描字符后到達(dá)狀態(tài)。對(duì)于有限狀態(tài)自動(dòng)機(jī),給定字母表上的串;初始時(shí),自動(dòng)機(jī)處于開始狀態(tài);從左到右逐個(gè)字符地掃描串;在的作用下,自動(dòng)機(jī)處于狀態(tài),在的作用下,自動(dòng)機(jī)處于狀態(tài),當(dāng)將串掃描結(jié)束后,若自動(dòng)機(jī)處于某一個(gè)接收狀態(tài),則稱有限狀態(tài)自動(dòng)機(jī)能夠接收(識(shí)別)串。對(duì)于自動(dòng)機(jī)而言,從開始狀態(tài)開始,在掃描串的過程中,狀態(tài)逐個(gè)地變化,直到某個(gè)接收狀態(tài),把狀態(tài)的變化過程稱為自動(dòng)機(jī)的一條路徑,而這條路徑上所標(biāo)記的字符的連接,就是自動(dòng)機(jī)所識(shí)別的串。有時(shí)為了表述方便,也采用如下定義的
4、擴(kuò)展的狀態(tài)轉(zhuǎn)換函數(shù)即自動(dòng)機(jī)在一個(gè)狀態(tài)時(shí),掃描串后到達(dá)唯一確定的狀態(tài);換句話說,如果是一個(gè)字母,是一個(gè)字符串,那么并且對(duì)串,. 用表示被接收的語言,它在字母表上,即,則. 若語言對(duì)某個(gè)自動(dòng)機(jī)有,則稱語言為一個(gè)有限狀態(tài)語言。 有限狀態(tài)自動(dòng)機(jī)的瞬時(shí)描述是一個(gè)二元組,其中是輸入帶上還沒有被掃描到的字符串,F(xiàn)SC的當(dāng)前狀態(tài)為,讀頭將馬上掃描串的左邊第一個(gè)符號(hào)。有限狀態(tài)自動(dòng)機(jī)的初始格局為,接收格局為,其中是初始狀態(tài),是某個(gè)接收狀態(tài)。 有限狀態(tài)自動(dòng)機(jī)在下面兩種情形下停機(jī):(1) 輸入串掃描結(jié)束時(shí);(2) 有限狀態(tài)自動(dòng)機(jī)的當(dāng)前格局為,而自動(dòng)機(jī)沒有對(duì)應(yīng)的函數(shù)的定義,即沒有定義。在這種情形,可以補(bǔ)充定義一個(gè)特殊的
5、狀態(tài):陷阱狀態(tài),即。對(duì)于陷阱狀態(tài),對(duì)任何字母,定義.2.兩個(gè)例子例2.1 我們將構(gòu)造一個(gè)有限狀態(tài)自動(dòng)機(jī),它能識(shí)別上的語言.分析:語言的特點(diǎn)是語言中的每個(gè)串都包含連續(xù)的3個(gè)0,故FSC的狀態(tài)及其意義如下:(1):有限狀態(tài)自動(dòng)機(jī)的開始狀態(tài),也是重新尋找子串000時(shí)的狀態(tài);(2):有限狀態(tài)自動(dòng)機(jī)讀到第一個(gè)0,有可能是子串000的第一個(gè)0;(3):有限狀態(tài)自動(dòng)機(jī)在后又讀到一個(gè)0;(4):有限狀態(tài)自動(dòng)機(jī)在后又讀到一個(gè)0,這是唯一的接收狀態(tài)。因此,狀態(tài)轉(zhuǎn)移函數(shù)為接收狀態(tài)為.例2.2 構(gòu)造有限狀態(tài)自動(dòng)機(jī),識(shí)別上的語言,該語言的每個(gè)字符串看成二進(jìn)制數(shù)時(shí),代表的數(shù)字能整除3.分析:使用3個(gè)狀態(tài)分別代表已經(jīng)讀入的
6、數(shù)除以3的得到不同余數(shù)的等價(jià)類:(1):已經(jīng)讀入的數(shù)除以3,余數(shù)為0的輸入串的等價(jià)類;(2):已經(jīng)讀入的數(shù)除以3,余數(shù)為1的輸入串的等價(jià)類;(3):已經(jīng)讀入的數(shù)除以3,余數(shù)為2的輸入串的等價(jià)類;因?yàn)椴荒芙邮湛沾赃€需要一個(gè)開始狀態(tài)。設(shè)是當(dāng)前讀入的輸入串,則(1):在開始狀態(tài)讀入0時(shí),有,進(jìn)入狀態(tài);讀入1時(shí),有,進(jìn)入狀態(tài)。(2):能引導(dǎo)自動(dòng)機(jī)到達(dá)此狀態(tài)的是3的倍數(shù),因此。 a)在此狀態(tài)讀入0,引導(dǎo)自動(dòng)機(jī)到達(dá)下一狀態(tài)的輸入串為,則,這表明也屬于對(duì)應(yīng)的等價(jià)類。所以自動(dòng)機(jī)在狀態(tài)讀入0應(yīng)該繼續(xù)保持狀態(tài)。 b)在此狀態(tài)讀入1,引導(dǎo)自動(dòng)機(jī),到達(dá)下一狀態(tài)的輸入串為,則,這表明屬于對(duì)應(yīng)的等價(jià)類。所以自動(dòng)機(jī)在
7、狀態(tài)讀入1應(yīng)該進(jìn)入狀態(tài)。(3): 能引導(dǎo)自動(dòng)機(jī)到達(dá)此狀態(tài)的滿足。a)在此狀態(tài)讀入0,引導(dǎo)自動(dòng)機(jī)到達(dá)下一狀態(tài)的輸入串為,則,這表明屬于對(duì)應(yīng)的等價(jià)類。所以自動(dòng)機(jī)在狀態(tài)讀入0進(jìn)入狀態(tài)。b)在此狀態(tài)讀入1,引導(dǎo)自動(dòng)機(jī)到達(dá)下一狀態(tài)的輸入串為,則,這表明屬于對(duì)應(yīng)的等價(jià)類。所以自動(dòng)機(jī)在狀態(tài)讀入1進(jìn)入狀態(tài)。(4):能引導(dǎo)自動(dòng)機(jī)到達(dá)此狀態(tài)的滿足。 a)在此狀態(tài)讀入0,引導(dǎo)自動(dòng)機(jī)到達(dá)下一狀態(tài)的輸入串為,則,這表明屬于對(duì)應(yīng)的等價(jià)類。所以自動(dòng)機(jī)在狀態(tài)讀入0進(jìn)入狀態(tài)。b)在此狀態(tài)讀入1,引導(dǎo)自動(dòng)機(jī)到達(dá)下一狀態(tài)的輸入串為,則,這表明屬于對(duì)應(yīng)的等價(jià)類。所以自動(dòng)機(jī)在狀態(tài)讀入1繼續(xù)保持狀態(tài)。因此狀態(tài)轉(zhuǎn)換函數(shù)為接收狀態(tài)為。三 帶
8、輸出的有限狀態(tài)自動(dòng)機(jī)1. Moore機(jī)的原理Moore機(jī)的數(shù)學(xué)模型是一個(gè)六元組其中 1)的含義同有限狀態(tài)自動(dòng)機(jī)。 2)是輸出字母表。 3)是輸出函數(shù)。對(duì)于,表示Moore機(jī)在狀態(tài)時(shí)輸出。 Moore機(jī)在讀入輸入串的過程中,狀態(tài)不斷發(fā)生改變,并且在每個(gè)狀態(tài)上都有輸出。 對(duì)于輸入串序列,Moore機(jī)的輸出序列為這里因此,如果輸入串的長度為,那么Moore機(jī)的輸出串的長度為。2. Moore機(jī)的運(yùn)算示例例3.1 構(gòu)造一個(gè)Moore機(jī),若將輸入串當(dāng)作一個(gè)二進(jìn)制數(shù),則在讀入串的過程中,希望輸出已經(jīng)讀過的子串模3的余數(shù)。分析:因?yàn)槟?的余數(shù)只有0、1和2,所以輸出字母表,并設(shè)3個(gè)狀態(tài)(1):已經(jīng)讀入的數(shù)除
9、以3,余數(shù)為0的輸入串的等價(jià)類;(2):已經(jīng)讀入的數(shù)除以3,余數(shù)為1的輸入串的等價(jià)類;(3):已經(jīng)讀入的數(shù)除以3,余數(shù)為2的輸入串的等價(jià)類;像例2.2那樣,狀態(tài)轉(zhuǎn)換函數(shù)為根據(jù)狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果,輸出函數(shù)為 例如當(dāng)輸入空串時(shí),輸出余數(shù)為0;當(dāng)輸入1010時(shí),狀態(tài)變換的序列為對(duì)應(yīng)的輸出序列為01221。3. Mealy機(jī)的原理Mealy機(jī)的數(shù)學(xué)模型是一個(gè)六元組其中1)的含義同有限狀態(tài)自動(dòng)機(jī)。 2)是輸出字母表。 3)是輸出函數(shù)。對(duì)于,表示Moore機(jī)在狀態(tài),讀入字母時(shí),輸出。 Mealy機(jī)在讀入串的過程中,狀態(tài)不斷發(fā)生改變,并且在每個(gè)狀態(tài)上,讀入某個(gè)字母時(shí),Mealy機(jī)都有輸出。 對(duì)于輸入串序列,Mealy機(jī)的輸出序列為這里因此,如果輸入串的長度為,那么Moore機(jī)的輸出串的長度也為。4. Mealy機(jī)的運(yùn)算示例例3.2 構(gòu)造一個(gè)只有兩個(gè)輸出符號(hào)的Mealy機(jī),對(duì)于上的語言,當(dāng)讀過的輸入串屬于時(shí),Mealy機(jī)輸出,表示接收;當(dāng)讀過的輸入串不屬于時(shí),Mealy機(jī)輸出,表示拒絕。分析:定義3個(gè)狀態(tài)(1):開始狀態(tài)。(2):自動(dòng)機(jī)讀入的字符是0。(3):自動(dòng)機(jī)讀入的字符是1。那么(1):若即將讀入0,則自動(dòng)機(jī)進(jìn)入狀態(tài),同時(shí)輸出;若即將讀入1,則自動(dòng)機(jī)進(jìn)入狀態(tài),同時(shí)輸出。(2):若即將讀入0,則自動(dòng)機(jī)保持狀態(tài),同時(shí)輸出;若即將讀入1,則自動(dòng)機(jī)進(jìn)入狀態(tài),同
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 農(nóng)產(chǎn)品批發(fā)市場(chǎng)合作運(yùn)營協(xié)議
- 智能工廠智能生產(chǎn)線控制系統(tǒng)開發(fā)協(xié)議
- 委托加工制造合同及質(zhì)量保證條款
- 浙江國企招聘2025臺(tái)州市城市建設(shè)投資發(fā)展集團(tuán)有限公司招聘12人筆試參考題庫附帶答案詳解
- 2025重慶聯(lián)合產(chǎn)權(quán)交易所集團(tuán)股份有限公司招聘31人筆試參考題庫附帶答案詳解
- 質(zhì)量安全員試題及答案
- 2025冶金工業(yè)信息標(biāo)準(zhǔn)研究院招聘筆試參考題庫附帶答案詳解
- 電商產(chǎn)業(yè)園發(fā)展前景分析報(bào)告
- 紡織品設(shè)計(jì)師證書考試?yán)砟羁偨Y(jié)試題及答案
- 淘寶平臺(tái)客戶關(guān)系管理(CRM)戰(zhàn)略與實(shí)踐
- 電工電子學(xué)知到智慧樹章節(jié)測(cè)試課后答案2024年秋湖南大學(xué)
- 2024年高考物理試題(廣東卷) 含答案
- 陜西延長石油集團(tuán)有限責(zé)任公司行測(cè)筆試題庫2024
- 【MOOC】計(jì)算機(jī)網(wǎng)絡(luò)-南京農(nóng)業(yè)大學(xué) 中國大學(xué)慕課MOOC答案
- 《預(yù)裝式變電站》課件
- 北京工業(yè)大學(xué)《環(huán)境微生物學(xué)》2022-2023學(xué)年第一學(xué)期期末試卷
- 汽車修理工(技師)考試題庫(含答案)
- 《循環(huán)神經(jīng)網(wǎng)絡(luò)》課件
- 新能源技術(shù)投資風(fēng)險(xiǎn)評(píng)估與管理策略考核試卷
- 2023北京朝陽區(qū)初三一模英語試題及參考答案
- 2024年浙江省中考社會(huì)試卷真題(含標(biāo)準(zhǔn)答案及評(píng)分標(biāo)準(zhǔn))
評(píng)論
0/150
提交評(píng)論