woaidongmao

文章均收錄自他人博客，但不喜標(biāo)題前加-[轉(zhuǎn)貼]，因其丑陋，見(jiàn)諒！~

隨筆 - 1469, 文章 - 0, 評(píng)論 - 661, 引用 - 0

數(shù)據(jù)加載中……

確定有限狀態(tài)自動(dòng)機(jī)---- 維基百科

src:

http://zh.wikipedia.org/wiki/%E7%A1%AE%E5%AE%9A%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E8%87%AA%E5%8A%A8%E6%9C%BA

維基百科，自由的百科全書(shū)

在計(jì)算理論中，確定有限狀態(tài)自動(dòng)機(jī)或確定有限自動(dòng)機(jī)（英：deterministic finite automaton；簡(jiǎn)稱：DFA）是一個(gè)能實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移的自動(dòng)機(jī)。對(duì)于一個(gè)給定的屬于該自動(dòng)機(jī)的狀態(tài)和一個(gè)屬于該自動(dòng)機(jī)字母表 $Σ$ 的字符，它都能根據(jù)事先給定的轉(zhuǎn)移函數(shù)轉(zhuǎn)移到下一個(gè)狀態(tài)（這個(gè)狀態(tài)有可能就是先前那個(gè)狀態(tài)）。

[編輯] 基礎(chǔ)概念

[編輯] 定義

確定有限狀態(tài)自動(dòng)機(jī) $clip_image001$ 是由

一個(gè)非空有限狀態(tài)的集合 Q
一個(gè)輸入字母表 $Σ$ （非空有限字符的集合）
一個(gè)轉(zhuǎn)移函數(shù) $clip_image002$ （例如： $clip_image003$ ）
一個(gè)開(kāi)始狀態(tài) $clip_image004$
一個(gè)接受狀態(tài)的集合 $clip_image005$

所組成的5-元組。因此一個(gè)DFA可以寫(xiě)成這樣的形式： $clip_image006$ 。

[編輯] 非正式的語(yǔ)義

確定有限狀態(tài)自動(dòng)機(jī)一個(gè)字符接一個(gè)字符的讀入一個(gè)字符串 $clip_image007$ ，并根據(jù)給定的轉(zhuǎn)移函數(shù)一步一步的轉(zhuǎn)移至下一個(gè)狀態(tài)。在讀完該字符串后，如果該自動(dòng)機(jī)停在一個(gè)屬于F的接受狀態(tài)，那么它就接受該字符串，反之則拒絕該字符串。

[編輯] 擴(kuò)展轉(zhuǎn)移函數(shù)

為了能夠?qū)?/span>DFA的命題進(jìn)行證明，需要一個(gè)數(shù)學(xué)上的正式的語(yǔ)義定義。

為此我們定義一個(gè)擴(kuò)展的轉(zhuǎn)移函數(shù) $clip_image008$ 。

$clip_image009$ 是自動(dòng)機(jī)從狀態(tài)q順序讀入字符串w后達(dá)到的那個(gè)狀態(tài)
擴(kuò)展轉(zhuǎn)移函數(shù)遞歸的定義為：

[編輯] 正式的語(yǔ)義

對(duì)于一個(gè)確定有限狀態(tài)自動(dòng)機(jī) $clip_image006$ ，如果 $clip_image012$ ，我們就說(shuō)該自動(dòng)機(jī)接受字符串w，反之則表明該自動(dòng)機(jī)拒絕字符串w。

被一個(gè)確定有限自動(dòng)機(jī)接受的語(yǔ)言（或者叫“被識(shí)別的語(yǔ)言”）定義為： $clip_image013$ 接受字符串 $clip_image014$ ，也就是由所有被接受的字符串組成的集合。

[編輯] 利弊

DFA 是最實(shí)際的計(jì)算模型，因?yàn)橛衅椒驳木€性時(shí)間、恒定空間的在線算法模擬在輸入流上的 DFA。給定兩個(gè) DFA 有有效算法找到識(shí)別它們所識(shí)別語(yǔ)言的并集、交集和補(bǔ)集 DFA。還有有效算法確定一個(gè) DFA 是否接受任何字符串，一個(gè) DFA 是否接受所有字符串，兩個(gè) DFA 是否識(shí)別同樣的語(yǔ)言，和對(duì)特定正則語(yǔ)言找到有極小數(shù)目個(gè)狀態(tài)的 DFA。

在另一方面，DFA 在可識(shí)別的語(yǔ)言上有嚴(yán)格的限制 — 很多簡(jiǎn)單的語(yǔ)言，包括需要多于恒定空間來(lái)解決的任何問(wèn)題，不能被 DFA 識(shí)別。經(jīng)典的 DFA 不能識(shí)別的簡(jiǎn)單語(yǔ)言的例子是括號(hào)語(yǔ)言，就是由正確配對(duì)的括號(hào)組成的語(yǔ)言，比如 (()())。由形如 aⁿbⁿ 的字符串組成的語(yǔ)言，就是有限數(shù)目個(gè) a，隨后是相等數(shù)目個(gè) b。可以證明沒(méi)有 DFA 有足夠狀態(tài)來(lái)識(shí)別這種語(yǔ)言。

[編輯] 其它

1. 能被確定有限狀態(tài)自動(dòng)機(jī)識(shí)別的語(yǔ)言是正則語(yǔ)言。

2. 確定有限狀態(tài)自動(dòng)機(jī)是非確定有限狀態(tài)自動(dòng)機(jī)的一種極限形式。

3. 確定有限狀態(tài)自動(dòng)機(jī)在計(jì)算能力上等價(jià)于非確定有限狀態(tài)自動(dòng)機(jī)。

4. 沒(méi)有接受狀態(tài)列表并沒(méi)有指定開(kāi)始狀態(tài)的確定有限狀態(tài)機(jī)叫做轉(zhuǎn)移系統(tǒng)或半自動(dòng)機(jī)。

[編輯] 例子

下面是一個(gè)確定有限狀態(tài)自動(dòng)機(jī)的例子。

$clip_image001$ 的狀態(tài)圖

確定有限狀態(tài)自動(dòng)機(jī) $clip_image006$

$Q$ $= {S 1, S 2}$
$Σ$ $= {0,1}$
$s$ $= S 1$
$F$ $= {S 1}$
$δ$ 由下面的狀態(tài)轉(zhuǎn)移表定義:

	0	1
S₁	S₂	S₁
S₂	S₁	S₂

對(duì)應(yīng)的轉(zhuǎn)移函數(shù)為：

$δ$ $(S 1,0) = S 2$
$δ$ $(S 1,1) = S 1$
$δ$ $(S 2,0) = S 1$
$δ$ $(S 2,1) = S 2$

狀態(tài) $S$ $1$ 表示在輸入的字符串中有偶數(shù)個(gè)0，而 $S$ $2$ 表示有奇數(shù)個(gè)0。在輸入中1不改變自動(dòng)機(jī)的狀態(tài)。當(dāng)讀完輸入的字符串的時(shí)候，狀態(tài)將顯示輸入的字符串是否包含偶數(shù)個(gè)0。

$clip_image001$ 能識(shí)別的的語(yǔ)言是 $clip_image018$ 。用正則表達(dá)式表示為： $(1 * (01 * 0) *) *$ 。

[編輯] 封閉性及一些運(yùn)算

[編輯] 封閉性

確定有限狀態(tài)自動(dòng)機(jī)的交，并，差，補(bǔ)，連接，替換，同態(tài)，逆同態(tài)等運(yùn)算是封閉的，也就是說(shuō)確定有限狀態(tài)自動(dòng)機(jī)通過(guò)這些運(yùn)算產(chǎn)生的新的自動(dòng)機(jī)也是確定有限狀態(tài)自動(dòng)機(jī)。

[編輯] 補(bǔ)運(yùn)算

$clip_image006$ 是一個(gè)DFA，那么由補(bǔ)運(yùn)算產(chǎn)生的新DFA定義為： $clip_image019$ 。顯然只要將 $clip_image001$ 中接受的狀態(tài)設(shè)為不接受的狀態(tài)，同時(shí)把不接受的狀態(tài)設(shè)為接受的狀態(tài)就得到 $clip_image020$ 。補(bǔ)運(yùn)算的復(fù)雜度是： $clip_image021$ 。

[編輯] 交運(yùn)算和并運(yùn)算

有兩個(gè)DFA， $clip_image022$ 和 $clip_image023$ ，那么由這兩個(gè)DFA創(chuàng)造出來(lái)的新的自動(dòng)機(jī)定義為： $clip_image024$ 。其中 $clip_image025$ ， $clip_image026$ 為 $clip_image027$ 的開(kāi)始狀態(tài)， $clip_image028$ 為 $clip_image027$ 的轉(zhuǎn)移函數(shù)，且作如下定義： $clip_image029$ 。

1. 當(dāng) $clip_image030$ 時(shí)，由上述方法得到的 $clip_image027$ 就是DFA $clip_image031$ 和 $clip_image032$ 的交運(yùn)算，記作： $clip_image033$ 。也就是說(shuō)對(duì)于讀入的字符串w，當(dāng)且僅當(dāng) $clip_image031$ 和 $clip_image032$ 同時(shí)接受w的時(shí)候 $clip_image027$ 接受w。

2. 當(dāng) $clip_image034$ 時(shí)，由上述方法得到的 $clip_image027$ 就是DFA $clip_image031$ 和 $clip_image032$ 的并運(yùn)算，記作： $clip_image035$ 。也就是說(shuō)對(duì)于讀入的字符串w，只要 $clip_image031$ 或 $clip_image032$ 中至少有一個(gè)接受w， $clip_image027$ 就接受w。

交運(yùn)算和并運(yùn)算的復(fù)雜度都是 $clip_image036$ 。

[編輯] 同態(tài)和逆同態(tài)運(yùn)算

一個(gè)同態(tài)函數(shù) $clip_image037$ 可以遞歸的定義為：

于是則有 $clip_image040$ 。（以上所述中 $clip_image041$ 為空字符， $clip_image042$ ）

1. $clip_image043$ ：對(duì)于接受語(yǔ)言L的DFA，只要將其中代表 $clip_image044$ 的邊替換成一個(gè)序列 $clip_image045$ 并在其中加入不屬于原DFA狀態(tài)的新?tīng)顟B(tài)，就產(chǎn)生了接受語(yǔ)言h(L)的DFA。

2. $clip_image046$ ：定義一個(gè) $clip_image047$ 都不變的新DFA，并定義新的轉(zhuǎn)移函數(shù)為 $clip_image048$ ，則 $clip_image049$ 就是逆同態(tài)運(yùn)算產(chǎn)生的新DFA。

此外替換運(yùn)算和逆同態(tài)運(yùn)算的方法近似。

[編輯] 最小自動(dòng)機(jī)

[編輯] 等價(jià)類(lèi)自動(dòng)機(jī)

對(duì)于一個(gè)正則語(yǔ)言，接受該語(yǔ)言的等價(jià)類(lèi)自動(dòng)機(jī)是一個(gè) $clip_image050$ 的5-元組。其定義如下：

Q是等價(jià)關(guān)系 ~_L 的等價(jià)類(lèi)的集合： $clip_image051$ 的集合
$clip_image052$
$clip_image053$
$clip_image054$

~_L 被稱為Nerode關(guān)系，是Myhill-Nerode定理的基礎(chǔ)。簡(jiǎn)單的來(lái)說(shuō)就是對(duì)于任意 $clip_image055$ ，如果 $clip_image056$ ，那么 x~_Ly 。

[編輯] 唯一性

對(duì)于任意給定的確定有限狀態(tài)自動(dòng)機(jī)都能找到一個(gè)與之計(jì)算能力等價(jià)的最小確定有限狀態(tài)自動(dòng)機(jī)，簡(jiǎn)稱最小自動(dòng)機(jī)。該最小自動(dòng)機(jī)中狀態(tài)的數(shù)量等于能識(shí)別相同語(yǔ)言的等價(jià)類(lèi)自動(dòng)機(jī)中等價(jià)關(guān)系的數(shù)量，我們可以稱最小自動(dòng)機(jī)和等價(jià)類(lèi)自動(dòng)機(jī)“實(shí)際上”是相等的，也就是同構(gòu)。非正式的說(shuō)法是：對(duì)于最小自動(dòng)機(jī)上的任意狀態(tài)都可以通過(guò)一個(gè)同構(gòu)函數(shù)變換成等價(jià)類(lèi)自動(dòng)機(jī)上的一個(gè)狀態(tài)。

能識(shí)別一個(gè)正則語(yǔ)言的等價(jià)類(lèi)自動(dòng)機(jī)是唯一的，因此能識(shí)別該語(yǔ)言的最小自動(dòng)機(jī)也是唯一的。

[編輯] 算法

定義一個(gè)非等價(jià)關(guān)系： $clip_image057$ ，如下步驟可以得到這個(gè)集合N：

1. 如果 $clip_image058$ ，就給所有的狀態(tài)對(duì)(p,q)和(q,p)打上標(biāo)記

2. 重復(fù)步驟3，直到所標(biāo)記的狀態(tài)對(duì)沒(méi)有變化為止

3. 對(duì)于未標(biāo)記的狀態(tài)對(duì)(p,q)和σ，如果 $clip_image059$ 被標(biāo)記過(guò)了就把(p,q)也標(biāo)記上

4. 以上所有標(biāo)記了的狀態(tài)對(duì)的集合就是非等價(jià)關(guān)系N

以下是由一個(gè)任意DFA轉(zhuǎn)換到一個(gè)最小DFA的步驟：

1. 把所有不能從開(kāi)始狀態(tài)達(dá)到的狀態(tài)刪除

2. 通過(guò)上述標(biāo)記算法計(jì)算非等價(jià)關(guān)系N

3. 一步一步將不屬于N的狀態(tài)對(duì)中的兩個(gè)狀態(tài)合成一個(gè)狀態(tài)

這樣就得到了接受相同語(yǔ)言的最小自動(dòng)機(jī)。復(fù)雜度為 $clip_image060$ 。

[編輯] 引用

Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. Section 1.1: Finite Automata, pp.31–47. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp.152–155.4.4 DFA can accept only regular language

自動(dòng)機(jī)理論: 形式語(yǔ)言和形式文法
喬姆斯基層級(jí)	文法	語(yǔ)言	極小自動(dòng)機(jī)
類(lèi)型 0	無(wú)限制	遞歸可枚舉	圖靈機(jī)
n/a	(無(wú)公用名)	遞歸	判定器
類(lèi)型 1	上下文有關(guān)	上下文有關(guān)	線性有界
n/a	附標(biāo)	附標(biāo)	嵌套堆棧
n/a	樹(shù)-鄰接	適度上下文有關(guān)	嵌入下推
類(lèi)型 2	上下文無(wú)關(guān)	上下文無(wú)關(guān)	非確定下推
n/a	確定上下文無(wú)關(guān)	確定上下文無(wú)關(guān)	確定下推
類(lèi)型 3	正則	正則	有限
每個(gè)語(yǔ)言或文法范疇都是其直接上面的范疇的真子集。

來(lái)自“http://zh.wikipedia.org/wiki/%E7%A1%AE%E5%AE%9A%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E8%87%AA%E5%8A%A8%E6%9C%BA”

posted on 2009-11-04 18:20 肥仔閱讀(2933) 評(píng)論(0) 編輯收藏引用所屬分類(lèi): 狀態(tài)機(jī) & 自動(dòng)機(jī) & 形式語(yǔ)言

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 自動(dòng)機(jī)，善用離開(kāi)事件 C語(yǔ)言詳解 - 表達(dá)式和語(yǔ)句棧的應(yīng)用-表達(dá)式求值（后綴式）編譯原理實(shí)驗(yàn)：后綴式求值（c++） FIRST集和FOLLOW集我們能不能說(shuō)不符合LR(1)的文法等價(jià)于二義文法？用C++編寫(xiě)簡(jiǎn)單繪圖語(yǔ)言的語(yǔ)法分析器并行狀態(tài)與串行狀態(tài)的等價(jià)性基于有限狀態(tài)機(jī)的工控系統(tǒng)軟件設(shè)計(jì) 以基本模型為胎，添加約束，從簡(jiǎn)到繁，可以構(gòu)造精確的系統(tǒng)模型

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品