Atitit 四種自動(dòng)機(jī) fsm pda

?

目錄

1. 自動(dòng)機(jī)可分為有限自動(dòng)機(jī)、后進(jìn)先出自動(dòng)機(jī)、線(xiàn)性有界自動(dòng)機(jī)、圖靈機(jī)等幾種。它們對(duì)語(yǔ)言的識(shí)別能力各不相同。 2

1.1. 抽象自動(dòng)機(jī)的理論。 2

1.2. 自動(dòng)機(jī)就是語(yǔ)言的解釋器?ati總結(jié) 2

1.3. 四種形式語(yǔ)言四種文法對(duì)應(yīng)四種自動(dòng)機(jī) 2

2. 四種自動(dòng)機(jī) fsm pda lba turin 2

2.1. FSM "finite state machine"有限狀態(tài)自動(dòng)機(jī)(FSM "finite state machine??正則語(yǔ)言機(jī)器 2

2.2. 圖靈機(jī)模型（無(wú)限狀態(tài)的自動(dòng)機(jī)）;用來(lái)描述通用計(jì)算機(jī)計(jì)算能力的圖靈機(jī)模型; 2

2.3. PDA下推自動(dòng)機(jī);push down automata 3

2.4. LBA線(xiàn)性有界自動(dòng)機(jī) (linear bounded automaton)上下文有關(guān)語(yǔ)言的識(shí)別接受器。 3

3. 對(duì)語(yǔ)言的識(shí)別能力上講：?有限狀態(tài)自動(dòng)機(jī)<非確定下推自動(dòng)機(jī)<線(xiàn)性有界非確定圖靈機(jī)<圖靈機(jī)（無(wú)限狀態(tài)的自動(dòng)機(jī)） 3

4. 其他類(lèi)型自動(dòng)機(jī) 3

5. 四大文法 4

5.1. 0型文法（對(duì)應(yīng)圖靈機(jī)）也稱(chēng)短語(yǔ)文法，記為PSG。 4

5.2. 1型文法（對(duì)應(yīng)線(xiàn)性界線(xiàn)自動(dòng)機(jī)，自然語(yǔ)言）上下文有關(guān)文法，記為CSG。 4

5.3. 2型文法（對(duì)應(yīng)下推自動(dòng)機(jī)，程序設(shè)計(jì)語(yǔ)言）上下文無(wú)關(guān)文法，記為CFG。 4

5.4. 3型文法（對(duì)應(yīng)有限自動(dòng)機(jī)）也叫正規(guī)文法，記為RG。 4

6. ref 5

?

?

1.?自動(dòng)機(jī)可分為有限自動(dòng)機(jī)、后進(jìn)先出自動(dòng)機(jī)、線(xiàn)性有界自動(dòng)機(jī)、圖靈機(jī)等幾種。它們對(duì)語(yǔ)言的識(shí)別能力各不相同。1.1.?抽象自動(dòng)機(jī)的理論。

抽象自動(dòng)機(jī)是一種能夠識(shí)別語(yǔ)言的抽象的裝置，它不是具有物理實(shí)體的機(jī)器，而是表示計(jì)算機(jī)運(yùn)算方式的抽象的邏輯關(guān)系系統(tǒng)，這樣的抽象自動(dòng)機(jī)可以用來(lái)檢驗(yàn)輸入的符號(hào)串是不是語(yǔ)言中合格的句子，如果是合格的句子，自動(dòng)機(jī)就接收它，如果不是，就不接收它。如圖所示:

1.2.?自動(dòng)機(jī)就是語(yǔ)言的解釋器?ati總結(jié)1.3.?四種形式語(yǔ)言四種文法對(duì)應(yīng)四種自動(dòng)機(jī)2.?四種自動(dòng)機(jī) fsm pda lba turin

?

2.1.?FSM "finite state machine"有限狀態(tài)自動(dòng)機(jī)(FSM "finite state machine??正則語(yǔ)言機(jī)器

計(jì)算能力

確定有限狀態(tài)自動(dòng)機(jī)與非確定有限狀態(tài)自動(dòng)機(jī)識(shí)別的語(yǔ)言都是正則語(yǔ)言。由于正則語(yǔ)言的良好性質(zhì)，許多為其他自動(dòng)機(jī)(下推自動(dòng)機(jī)或圖靈機(jī))不能判定的問(wèn)題，在有限狀態(tài)自動(dòng)機(jī)的情形下，都可以得到判定，并且存在有效的算法。

?

2.2.?圖靈機(jī)模型（無(wú)限狀態(tài)的自動(dòng)機(jī)）;用來(lái)描述通用計(jì)算機(jī)計(jì)算能力的圖靈機(jī)模型;

圖靈機(jī)（無(wú)限狀態(tài)的自動(dòng)機(jī)）

2.3.?PDA下推自動(dòng)機(jī);push down automata

?

2.4.?LBA線(xiàn)性有界自動(dòng)機(jī) (linear bounded automaton)上下文有關(guān)語(yǔ)言的識(shí)別接受器。

?

一種圖靈機(jī).是把計(jì)算限制在僅僅包含輸人的那一段帶上的圖靈機(jī).可用作上下文有關(guān)語(yǔ)言的識(shí)別接受器。

線(xiàn)性有界自動(dòng)機(jī)(縮寫(xiě)為L(zhǎng)BA)可形式地由M=<K,}',1',8,qo,F)來(lái)表示.其中:K是狀態(tài)的有限集;尸是帶符號(hào)的有限集;}}1'是輸人符號(hào)集;K中的q。是起始狀態(tài);FcK是終結(jié)狀態(tài)集;8是從KXI'到KXI'X {L,R}子集的映射，<L,R)分別是讀寫(xiě)頭左右移一格.刃含有兩個(gè)特殊的符號(hào)，通常記為本和$，它們分別是左端標(biāo)志和右端標(biāo)志.這些符號(hào)開(kāi)始就處在輸人帶的端點(diǎn)，其作用是阻止帶頭離開(kāi)帶上出現(xiàn)符號(hào)的區(qū).

3.?對(duì)語(yǔ)言的識(shí)別能力上講：
有限狀態(tài)自動(dòng)機(jī)<非確定下推自動(dòng)機(jī)<線(xiàn)性有界非確定圖靈機(jī)<圖靈機(jī)（無(wú)限狀態(tài)的自動(dòng)機(jī)）4.?其他類(lèi)型自動(dòng)機(jī)

由下推表組成的單項(xiàng)非確定程序的下推自動(dòng)機(jī);

線(xiàn)性有界自動(dòng)機(jī);

用來(lái)描述通用計(jì)算機(jī)計(jì)算能力的圖靈機(jī)模型;

進(jìn)行與轉(zhuǎn)移函數(shù)，轉(zhuǎn)移狀態(tài)有關(guān)輸出的時(shí)序機(jī);

由一些基本語(yǔ)句構(gòu)成程序框圖的波斯特機(jī);隨即存儲(chǔ)機(jī);

堆棧自動(dòng)機(jī);

不受有限自動(dòng)機(jī)做控制器和存儲(chǔ)限制的無(wú)限自動(dòng)機(jī);

統(tǒng)計(jì)自動(dòng)機(jī)某一條件概率分布的概率自動(dòng)機(jī)和細(xì)胞自動(dòng)機(jī)。

?

5.?四大文法

一般的文法至少都是0型文法，也就是說(shuō)0型文法限制最少。若將0型文法比作基類(lèi)的話(huà)，1、2、3型文法就是不斷繼承并加以限制得到的子類(lèi)。
文法表示過(guò)程中，常用大寫(xiě)字母表示非終結(jié)符V_N，而小寫(xiě)字母表示的是終結(jié)符V_T。

?

5.1.?0型文法（對(duì)應(yīng)圖靈機(jī)）也稱(chēng)短語(yǔ)文法，記為PSG。

·?一個(gè)非常重要的理論結(jié)果是：0型文法的能力相當(dāng)于圖靈機(jī)?；蛘哒f(shuō)，任何0型文語(yǔ)言都是遞歸可枚舉的，反之，遞歸可枚舉集必定是一個(gè)0型語(yǔ)言。

5.2.?1型文法（對(duì)應(yīng)線(xiàn)性界線(xiàn)自動(dòng)機(jī)，自然語(yǔ)言）上下文有關(guān)文法，記為CSG。

·?此文法對(duì)應(yīng)于線(xiàn)性有界自動(dòng)機(jī)。

5.3.?2型文法（對(duì)應(yīng)下推自動(dòng)機(jī)，程序設(shè)計(jì)語(yǔ)言）上下文無(wú)關(guān)文法，記為CFG。

·??2型文法也叫上下文無(wú)關(guān)文法，記為CFG。

·?此文法對(duì)應(yīng)于下推自動(dòng)機(jī)。

?

5.4.?3型文法（對(duì)應(yīng)有限自動(dòng)機(jī)）也叫正規(guī)文法，記為RG。

·?它是在2型文法的基礎(chǔ)上滿(mǎn)足:A→α|αB（右線(xiàn)性）或A→α|Bα（左線(xiàn)性）。

·?3型文法也叫正規(guī)文法，記為RG。

·?此文法對(duì)應(yīng)于有限狀態(tài)自動(dòng)機(jī)。

?