Atitit 四種自動機 fsm pda
?
目錄
1. 自動機可分為有限自動機、后進先出自動機、線性有界自動機、圖靈機等幾種。它們對語言的識別能力各不相同。 2
1.1. 抽象自動機的理論。 2
1.2. 自動機就是語言的解釋器?ati總結(jié) 2
1.3. 四種形式語言四種文法對應四種自動機 2
2. 四種自動機 fsm pda lba turin 2
2.1. FSM "finite state machine"有限狀態(tài)自動機(FSM "finite state machine??正則語言機器 2
2.2. 圖靈機模型（無限狀態(tài)的自動機）;用來描述通用計算機計算能力的圖靈機模型; 2
2.3. PDA下推自動機;push down automata 3
2.4. LBA線性有界自動機 (linear bounded automaton)上下文有關語言的識別接受器。 3
3. 對語言的識別能力上講：?有限狀態(tài)自動機<非確定下推自動機<線性有界非確定圖靈機<圖靈機（無限狀態(tài)的自動機） 3
4. 其他類型自動機 3
5. 四大文法 4
5.1. 0型文法（對應圖靈機）也稱短語文法，記為PSG。 4
5.2. 1型文法（對應線性界線自動機，自然語言）上下文有關文法，記為CSG。 4
5.3. 2型文法（對應下推自動機，程序設計語言）上下文無關文法，記為CFG。 4
5.4. 3型文法（對應有限自動機）也叫正規(guī)文法，記為RG。 4
6. ref 5
?
?
1.?自動機可分為有限自動機、后進先出自動機、線性有界自動機、圖靈機等幾種。它們對語言的識別能力各不相同。1.1.?抽象自動機的理論。
抽象自動機是一種能夠識別語言的抽象的裝置，它不是具有物理實體的機器，而是表示計算機運算方式的抽象的邏輯關系系統(tǒng)，這樣的抽象自動機可以用來檢驗輸入的符號串是不是語言中合格的句子，如果是合格的句子，自動機就接收它，如果不是，就不接收它。如圖所示:
1.2.?自動機就是語言的解釋器?ati總結(jié)1.3.?四種形式語言四種文法對應四種自動機2.?四種自動機 fsm pda lba turin
?
2.1.?FSM "finite state machine"有限狀態(tài)自動機(FSM "finite state machine??正則語言機器
計算能力
確定有限狀態(tài)自動機與非確定有限狀態(tài)自動機識別的語言都是正則語言。由于正則語言的良好性質(zhì)，許多為其他自動機(下推自動機或圖靈機)不能判定的問題，在有限狀態(tài)自動機的情形下，都可以得到判定，并且存在有效的算法。
?
2.2.?圖靈機模型（無限狀態(tài)的自動機）;用來描述通用計算機計算能力的圖靈機模型;
圖靈機（無限狀態(tài)的自動機）
2.3.?PDA下推自動機;push down automata
?
2.4.?LBA線性有界自動機 (linear bounded automaton)上下文有關語言的識別接受器。
?
一種圖靈機.是把計算限制在僅僅包含輸人的那一段帶上的圖靈機.可用作上下文有關語言的識別接受器。
線性有界自動機(縮寫為LBA)可形式地由M=<K,}',1',8,qo,F)來表示.其中:K是狀態(tài)的有限集;尸是帶符號的有限集;}}1'是輸人符號集;K中的q。是起始狀態(tài);FcK是終結(jié)狀態(tài)集;8是從KXI'到KXI'X {L,R}子集的映射，<L,R)分別是讀寫頭左右移一格.刃含有兩個特殊的符號，通常記為本和$，它們分別是左端標志和右端標志.這些符號開始就處在輸人帶的端點，其作用是阻止帶頭離開帶上出現(xiàn)符號的區(qū).
3.?對語言的識別能力上講：
有限狀態(tài)自動機<非確定下推自動機<線性有界非確定圖靈機<圖靈機（無限狀態(tài)的自動機）4.?其他類型自動機
由下推表組成的單項非確定程序的下推自動機;
線性有界自動機;
用來描述通用計算機計算能力的圖靈機模型;
進行與轉(zhuǎn)移函數(shù)，轉(zhuǎn)移狀態(tài)有關輸出的時序機;
由一些基本語句構(gòu)成程序框圖的波斯特機;隨即存儲機;
堆棧自動機;
不受有限自動機做控制器和存儲限制的無限自動機;
統(tǒng)計自動機某一條件概率分布的概率自動機和細胞自動機。
?
5.?四大文法
一般的文法至少都是0型文法，也就是說0型文法限制最少。若將0型文法比作基類的話，1、2、3型文法就是不斷繼承并加以限制得到的子類。
文法表示過程中，常用大寫字母表示非終結(jié)符VN，而小寫字母表示的是終結(jié)符VT。
?
5.1.?0型文法（對應圖靈機）也稱短語文法，記為PSG。
·?一個非常重要的理論結(jié)果是：0型文法的能力相當于圖靈機?；蛘哒f，任何0型文語言都是遞歸可枚舉的，反之，遞歸可枚舉集必定是一個0型語言。
5.2.?1型文法（對應線性界線自動機，自然語言）上下文有關文法，記為CSG。
·?此文法對應于線性有界自動機。
5.3.?2型文法（對應下推自動機，程序設計語言）上下文無關文法，記為CFG。
·??2型文法也叫上下文無關文法，記為CFG。
·?此文法對應于下推自動機。
?
5.4.?3型文法（對應有限自動機）也叫正規(guī)文法，記為RG。
·?它是在2型文法的基礎上滿足:A→α|αB（右線性）或A→α|Bα（左線性）。
·?3型文法也叫正規(guī)文法，記為RG。
·?此文法對應于有限狀態(tài)自動機。
?
下載文檔
