四種自動機及對應(yīng)文法 有限自動機 下推自動機 圖靈機 線性有界自動機

1、形式語言與自動機1參考文獻2參考文獻3參考文獻4背景5 圖靈機 1936年首先由圖靈（A. M. Turing）提出，他設(shè)計的自動機稱為圖靈機。背景6 有限狀態(tài)機 又被稱為有窮狀態(tài)自動機、有限自動機 1951年到1956年，克林(Kleene)在研究神經(jīng)細胞中，建立了識別語言的系統(tǒng)有限狀態(tài)機。背景7 丘奇（Church）提出了一個假設(shè)：圖靈機的計算能力代表著可實現(xiàn)的計算裝置的基本范圍。 任何能在電子計算機上實現(xiàn)的計算都能用圖靈機進行描述。背景8 形式語言 1956年，N. 喬姆斯基（Noam Chomsky）給出一種文法的數(shù)學(xué)模型。語言L定義為一個字母表中的字母組成的一些串的集合：L *。 字

2、母表上按照一定的規(guī)則定義一個文發(fā)(grammar)，該文法所產(chǎn)生的所有句子組成的集合就是該文法產(chǎn)生的語言。背景9 20世紀50年代，巴科斯范式(Backus Nour Form 或 Backus Normal Form, BNF)實現(xiàn)了對高級語言ALGOL-60的成功描述。這一成功，使得形式語言在20世紀60年代得到了大力的發(fā)展，并使形式語言與編譯原理緊密聯(lián)系在一起。 上述理論在編譯原理、人工智能、可計算性和時序邏輯電路設(shè)計等領(lǐng)域有著廣泛的應(yīng)用。語言理論10自然語言自然語言：人與人之間交流的基本手段。 如：漢語、英語、俄語、法語、等人工語言人工語言：主要用于人與計算機之間的交流。 如：程序設(shè)計

3、語言 語言自然語言人工語言語言理論11形式語言形式語言：研究自然語言和人工語言都必須遵循的一般規(guī)律 研究字符串集合及其性質(zhì)的學(xué)科Chomsky文法體系：4種類型的文法及其產(chǎn)生的語言 正規(guī)文法RG正規(guī)語言RL； 上下文無關(guān)文法CFG上下文無關(guān)語言CFL； 上下文有關(guān)文法CSG上下文有關(guān)語言CSL； 無限制文法URG遞歸可枚舉語言r.e.。自動機理論12語言（形式語言）識別器 4種類型自動機與4類文法相對應(yīng) 有限自動機FA RL RG 下推自動機PDA CFL CFG 線性界限自動機LBACSL CSG 圖靈機TMr.e.URG形式語言（Formal Language）13語言及其表示14 語言某

4、個字母表上滿足某些特定條件的字符串的集合自然語言人工語言1.11.1字母表、串和語言字母表、串和語言字母表（字母表（Alphabet）：由字符組成的非空有限集，通常用表示。(sigma 西格馬) 空 集 不能作為字母表 無限集 也不能作為字母表 a,b,c,d 0,1語言及其表示15語言及其表示16語言及其表示17語言及其表示18 串（串（String）：）：由某字符表上的字符組成的有限序列。例如：0100101 是字母表=0,1上的一個串。 串的長度串的長度：一個串中字符的個數(shù)。 設(shè)x為字母表上的一個串，x的長度記為|x|。例如 |0100101|=7空串：不含任何字符的串，即長度為零的串，

5、記為 。語言及其表示19前綴、后綴、子串語言及其表示20語言及其表示21串的逆：把一個串中的字符逆向順序重新排列得到的另一個串 設(shè)x為一個串，x的逆記為xR 例： 若x=0100101 則xR=1010010 易知 1）|xR|=|x| 2）空串的逆仍是空串：R=語言及其表示22串的連接（串的連接（concatenation）運算）運算語言及其表示23串的冪運算串的冪運算 串的連接運算又稱為串的乘法運算。類似于從數(shù)的乘法運算推廣到數(shù)的冪運算那樣，也可以從串的乘法推廣到串的冪運算。 設(shè)x為一個串，則定義 語言及其表示24語言及其表示25語言及其表示26語言（Language）語言及其表示27語言

6、幾種基本運算語言幾種基本運算 語言及其表示28語言及其表示29語言及其表示30 句型、推導(dǎo)與句子句型、推導(dǎo)與句子語言及其表示31文法所產(chǎn)生的語言文法所產(chǎn)生的語言語言及其表示32舉例舉例語言及其表示33語言及其表示34語言及其表示35 語言識別器語言識別器 語言識別器同文法一樣，都是對（可能為無限集的）語言提供有限表示的一種方式。語言識別器也稱為自動機。 如果說文法是從產(chǎn)生語言的角度來表示語言，那么自動機是從識別語言的角度來表示語言。 自動機的結(jié)構(gòu)可以大致表示成下圖的形式。輔助存儲器a1a2an有限狀態(tài)控制器圖 自動機的大致結(jié)構(gòu)語言及其表示36即自動機由部分組成：有限狀態(tài)器、輸入帶和輔助存儲器。

7、有的自動機可以沒有輔助存儲器。 輸入帶可以有限長或無限長，有限狀態(tài)控制器對輸入帶可以只允許讀，不允許寫，也可以讀和寫。 根據(jù)不同的規(guī)定，自動機可以分為幾種類型。正規(guī)文法與有限自動機37 正規(guī)語言是Chomsky文法體系中最簡單的一類語言。產(chǎn)生這種語言的文法是正規(guī)文法，識別這類語言的是有限自動機。此外，這類語言也可以用正規(guī)表達式表示。因此，正規(guī)語言也叫正規(guī)集。正規(guī)表達式與正規(guī)集38正規(guī)表達式與正規(guī)集39正規(guī)表達式的性質(zhì)40正規(guī)文法和正規(guī)語言41 正規(guī)文法是Chomsky文法體系中最簡單的一種文法。說它簡單，是指它的產(chǎn)生式的形式簡單，因為產(chǎn)生式集是一個文法的核心。 定義和例子 正規(guī)文法和正規(guī)語言4

8、2有限自動機（finite automaton,FA）43有限自動機（finite automaton,FA）4445確定的有限自動機確定的有限自動機46確定的有限自動機確定的有限自動機47確定的有限自動機確定的有限自動機48確定的有限自動機確定的有限自動機49確定的有限自動機確定的有限自動機50確定的有限自動機確定的有限自動機51確定的有限自動機確定的有限自動機52不確定的有限自動機不確定的有限自動機53不確定的有限自動機不確定的有限自動機54不確定的有限自動機不確定的有限自動機55不確定的有限自動機不確定的有限自動機56不確定的有限自動機不確定的有限自動機57不確定的有限自動機不確定的有限

9、自動機58帶輸出的有限自動機帶輸出的有限自動機59Moore機60Moore機61Moore機62Moore機63Moore機64Mealy機機65Mealy機機66Mealy機機67Mealy機機68Moore機和機和Mealy機的等價性機的等價性69上下文無關(guān)文法與下推自動機70上下文無關(guān)文法(context-free grammer）71上下文無關(guān)文法(context-free grammer）72上下文無關(guān)文法(context-free grammer）73上下文無關(guān)文法(context-free grammer）74上下文無關(guān)文法(context-free grammer）75推導(dǎo)樹

10、（derivation tree）76推導(dǎo)樹（derivation tree）77推導(dǎo)樹（derivation tree）78推導(dǎo)樹與推導(dǎo)的關(guān)系推導(dǎo)樹與推導(dǎo)的關(guān)系79最左推導(dǎo)與最右推導(dǎo)最左推導(dǎo)與最右推導(dǎo)80上下文無關(guān)文法的歧義性上下文無關(guān)文法的歧義性81上下文無關(guān)文法的歧義性上下文無關(guān)文法的歧義性82上下文無關(guān)文法的應(yīng)用上下文無關(guān)文法的應(yīng)用83上下文無關(guān)文法的應(yīng)用上下文無關(guān)文法的應(yīng)用84下推自動機（下推自動機（Pushdown Automaton）85下推自動機（下推自動機（Pushdown Automaton）86下推自動機（下推自動機（Pushdown Automaton）87下推自動機（

11、下推自動機（Pushdown Automaton）88下推自動機（下推自動機（Pushdown Automaton）89下推自動機（下推自動機（Pushdown Automaton）90下推自動機（下推自動機（Pushdown Automaton）91下推自動機（下推自動機（Pushdown Automaton）92n例：構(gòu)造PDA M，接受語言L(M)= anbnn1n思路：把輸入的字符a入棧，當(dāng)開始輸入b時，從棧中彈出a， 若a、b個數(shù)相同，則到達終態(tài)，且棧中空。n解：設(shè)PDA M（Q，T，q0，z0，F(xiàn)）， Qq0 ，q1 ，q2 q0 初態(tài)；接受a q1狀態(tài)；接受b q2狀態(tài)；輸入 回

12、到q0 Ta,b, = z0, a, F = q0定義為：(q0，a，z0) = ( q1 ，a z0) (q1，a，a) = ( q1 ，aa) (q1，b，a) = ( q2 ，) (q2，z0) = ( q0 ，) (q2，b，a) = ( q2 ，) 下推自動機（下推自動機（Pushdown Automaton）93 q a, Z/ p表示（p，）（q，a，Z）n上例的圖形表示： a, z0/az0 b, a/ a, a/aa b, a/, z0/q0q2q1用格局表示aabb的識別過程:(q0 ，aabb，z0)（q1，abb，az0） （q1，bb，aaz0） （q2，b，az0） （q2，z0） （q0，） 終態(tài)接受終態(tài)接受確定的下推自動機確定的下推自動機94無限制文法無限制文法95無限制文法無限制文法96圖靈機97圖靈機98圖靈機99圖靈機100圖靈機101圖靈機102圖靈機103圖靈機104圖靈機105圖靈機106圖靈機107上下文有關(guān)文法