自動機理論- 維基百科，自由的百科全書

自動機是有限狀態機（FSM）的數學模型。

FSM是給定符號輸入，依據（可表達為一個表格的）轉移函式「跳轉」過一系列狀態的一種機器。

自動機理論 維基百科，自由的百科全書 跳至導覽 跳至搜尋 在理論電腦科學中，自動機理論是對抽象機和它們能解決的問題的研究。

自動機理論密切關聯於形式語言理論，因為自動機經常按它們所能辨識的形式語言類來分類。

目次 1基本描述 2術語 3形式描述 4有限自動機的分類 4.1有限自動機的擴展 5有限狀態自動機的最小化 6計算能力與判定問題 7外部連結 8引用 基本描述[編輯] 自動機是有限狀態機（FSM）的數學模型。

FSM是給定符號輸入，依據（可表達為一個表格的）轉移函式「跳轉」過一系列狀態的一種機器。

在常見的FSM的「米利型有限狀態機」（Mealy）變體中，這個轉移函式告訴自動機給定當前狀態和當前字元的時候下一個狀態是什麼。

逐個讀取輸入中的符號，直到被完全耗盡(把它當作有一個字寫在其上的磁帶，通過自動機的讀磁頭來讀取它；磁頭在磁帶上前行移動，一次讀一個符號)。

一旦輸入被耗盡，自動機被稱為「停止」了。

依賴自動機停止時的狀態，稱呼這個自動機要麼是「接受」要麼「拒絕」這個輸入。

如果停止於「接受狀態」，則自動機「接受」了這個字。

在另一方面，如果它停止於「拒絕狀態」，則這個字被「拒絕」。

自動機接受的所有字的集合被稱為「這個自動機接受的語言」。

但要注意，自動機一般不必須有有限數目甚至可數個狀態。

比如，量子有限自動機有不可數無限個狀態，因為所有可能狀態的集合是在復投影空間中所有點的集合。

所以，量子有限自動機和有限狀態機一樣，都是更一般想法拓撲自動機的特殊情況，它的狀態的集合是拓撲空間，而狀態轉移函式取自在這個空間上的所有可能函式。

拓撲自動機經常叫做M-自動機，簡單是半自動機加上接受狀態集合的補充，這裡的集合交集確定初始狀態是被接受還是被拒絕。

一般地說，自動機不需要嚴格的接受或拒絕一個輸入；它可以按某個在零和一之間的概率接受它。

還是用量子有限自動機作為展範例子，它只按某個概率接受輸入。

這個想法也是更一般情況幾何自動機或度量自動機的特殊情況，它的狀態的集合是度量空間，一個語言被這個自動機接受如果在初始點和接受狀態的集合之間的距離關於這個度量是足夠的小。

術語[編輯] 自動機有如下基本概念： 符號 有某種意義或在這個機器上有效的任意資料(datum)。

符號有時就叫做「字母」。

字 通過一些符號串接而形成的有限字串。

字母表 符號的有限集合。

字母表經常指示為 Σ {\displaystyle\Sigma} ，它是在字母表中所有字母的集合。

語言 字的集合，由給定字母表中的符號形成。

可以是也可以不是無限的。

Kleene閉包 一個語言可以被認為是所有可能字的子集。

所有可能字的集合可以被認為是所有可能的字串串接的集合。

形式上說，所有可能字串的集合叫做自由么半群。

它被指示為 Σ ∗ {\displaystyle\Sigma^{*}} ，上標*被稱為Kleene星號。

形式描述[編輯] 自動機可以表示為5-元組 ⟨ Q , Σ , δ , q 0 , F ⟩ {\displaystyle\langleQ,\Sigma,\delta,q_{0},F\rangle} ，這裡的: Q是狀態的集合。

∑是符號的有限集合，我們稱為這個自動機接受的語言的字母表。

δ是轉移函式，就是 δ : Q × Σ → Q {\displaystyle\delta:Q\times\Sigma\rightarrowQ} 。

(對於非確定自動機，空字串是允許的輸入)。

q0是開始狀態，就是說自動機在還未處理輸入的時候的狀態(明顯的q0∈Q)。

F是叫做終止狀態的Q中的狀態的集合(就是F⊆Q)。

給定一個輸入字母 a ∈ Σ {\displaystylea\in\Sigma} ，可以使用簡單的currying技巧寫轉移函式為 δ a : Q → Q {\displaystyle\delta_{a}:Q\rightarrowQ} ，就是說，寫 δ ( q , a ) = δ a ( q ) {\displaystyle\delta(q,a)=\delta_{a}(q)} 對於所有 q ∈ Q {\displaystyleq\inQ} 。

這種方式下轉移可以被更簡單的看待:它就是「動作」於Q中一個狀態上的生成另一個狀態的某種東西。

你可以接著考慮重複的應用函式複合於各種函式 δ a {\displaystyle\delta_{a}} , δ b {\displaystyle\delta_{b}} 等等的結果。

重複的函式複合形成一個么半群。

對於轉移函式，這個么半群叫做轉移么半群，有時也叫做「變換半群」。

給定一對字母 a , b ∈ Σ {\displaystylea,b\in\Sigma} ，可以通過堅持 δ ^ a b = δ a ∘ δ b {\displaystyle{\widehat{\delta}}_{ab}=\delta_{a}\circ\delta_{b}} 定義一個新函式 δ ^ {\displaystyle{\widehat{\delta}}} ，這裡的 ∘ {\displaystyle\circ} 指示函式複合。

明顯的，可以遞迴的繼續這個過程，這樣就有了為所有字 w ∈ Σ ∗ {\displaystylew\in\Sigma^{*}} 定義的函式 δ ^ w {\displaystyle{\widehat{\delta}}_{w}} 的遞迴定義，因此有了對映 δ ^ : Q × Σ ⋆ → Q . {\displaystyle{\widehat{\delta}}:Q\times\Sigma^{\star}\rightarrowQ.} 這個構造也可以反過來:給定 δ ^ {\displaystyle{\widehat{\delta}}} ，可以重新構造一個 δ {\displaystyle\delta} ，因此兩個描述是等價的。

三元組 ⟨ Q , Σ , δ ⟩ {\displaystyle\langleQ,\Sigma,\delta\rangle} 被稱為半自動機。

半自動機位於自動機底下，它們就是忽略了開始狀態和接受狀態的自動機。

開始狀態和接受狀態的補充概念允許自動機做半自動機不能做的事情:它們可以辨識形式語言。

確定有限自動機 ⟨ Q , Σ , δ , q 0 , F ⟩ {\displaystyle\langleQ,\Sigma,\delta,q_{0},F\rangle} 接受的語言 L {\displaystyleL} 是: L = { w ∈ Σ ⋆ | δ ^ ( q 0 , w ) ∈ F } {\displaystyleL=\{w\in\Sigma^{\star}\,|\;{\widehat{\delta}}(q_{0},w)\inF\}} 就是說，一個自動機所接受的語言是在字母表 Σ {\displaystyle\Sigma} 之上所有字w的集合，當給定為自動機的輸入的時候，將導致它停止於 F {\displaystyleF} 中的某個狀態。

被自動機接受的語言叫做可辨識語言。

當狀態集合Q是有限的時候，自動機被稱為有限狀態自動機，而所有可辨識的語言是正規語言。

事實上，有一個強等價:對於所有正規語言，都有一個有限狀態自動機，反之亦然。

如上所述，集合Q不必須是有限或可數的；它可以採用一般的拓撲空間；這就得到了一般的拓撲自動機。

另一種可能的推廣是度量自動機或「幾何自動機」。

在這種情況下，改變了對語言的接受:替代在 δ ^ ( q 0 , w ) ∈ F {\displaystyle{\widehat{\delta}}(q_{0},w)\inF} 中的最終狀態的集合包含，以在最終狀態 δ ^ ( q 0 , w ) {\displaystyle{\widehat{\delta}}(q_{0},w)} 和集合 F {\displaystyleF} 之間的度量距離的方式給出。

特定類型的概率自動機是度量自動機，其度量空間是在概率空間上的測量。

有限自動機的分類[編輯] 下面是三類有限自動機 確定有限自動機(DFA) 對字母表中每個符號，自動機的狀態都有且僅有一個轉移。

DFA 非確定有限自動機(NFA) 自動機的狀態對字母表中的每個符號可以有也可以沒有轉移，對一個符號甚至可以有多個轉移。

自動機接受一個字，如果存在至少一個從q0到F中標記(label)著這個輸入字的一個狀態的路徑。

如果一個轉移是「未定義」的，自動機因此不知道如何繼續讀取輸入，則拒絕這個字。

等價於前面例子DFA的NFA 有ε轉移的非確定有限自動機(FND-ε或ε-NFA) 除了有能力對任何符號跳轉到更多狀態或沒有狀態可以跳轉之外，它們可以做根本不關於符號的跳轉。

就是說，如果一個狀態有標記著 ϵ {\displaystyle\epsilon} 的轉移，則NFA可以處在 ϵ {\displaystyle\epsilon} -轉移可到達的任何狀態中，直接或通過其他有 ϵ {\displaystyle\epsilon} -轉移的狀態。

從一個狀態q通過這種方法可到達的狀態的集合叫做q的 ϵ {\displaystyle\epsilon} -閉包。

儘管可以證明所有這些自動機都「可以接受同樣的語言」。

你總是可以構造接受與給定的NFAM同樣語言的某個DFAM。

有限自動機的擴充[編輯] 上述自動機接受的語言家族被稱為正規語言家族。

更強力的自動機可以接受更複雜的語言。

比如: 下推自動機(PDA) 這種機器等同於DFA(或NFA)，除了它們額外的裝備了棧形式的記憶體。

轉移函式 δ {\displaystyle\delta} 也依賴於在棧頂的符號，並在每次轉移時指定如何變更棧。

非確定PDA接受上下文無關語言。

線性有界自動機(LBA) LBA是有限制的圖靈機；不使用無限磁帶，它的磁帶有同輸入字串成正比的空間。

LBA接受上下文有關語言。

圖靈機 它們是最強力的電腦器。

它們擁有磁帶形式的無限記憶體，和可以讀取和變更磁帶的磁頭，它可在磁帶上向任何方向移動。

圖靈機等價於演算法，是現代電腦的理論基礎。

圖靈機判定遞迴語言並辨識遞迴可列舉語言。

有限狀態自動機的最小化[編輯] 主條目：確定有限狀態自動機最小化 根據Myhill-Nerode定理，在同構意義下接受一個正規語言的最少狀態的確定有限狀態自動機是唯一的。

同時我們還存在有效的演算法（時間開銷是O(n2)的）構造出與給定確定有限狀態自動機等價的最小化的確定有限狀態自動機。

計算能力與判定問題[編輯] 確定有限狀態自動機與非確定有限狀態自動機辨識的語言都是正規語言。

由於正規語言的良好性質，許多為其他自動機（下推自動機或圖靈機）不能判定的問題，在有限狀態自動機的情形下，都可以得到判定，並且存在有效的演算法。

對一個確定有限狀態自動機，下述判定問題都可以判定，並且存在有效的演算法。

該自動機辨識的語言是否為空集。

該自動機辨識的語言是否為有限集。

該自動機是否與另一個確定有限狀態自動機辨識同一個的語言。

外部連結[編輯] VisualAutomataSimulator（頁面存檔備份，存於網際網路檔案館） JFLAP ProyectoSEPa(inSpanish) Exorciser(inGerman) 參照[編輯] JohnE.Hopcroft,RajeevMotwani,JeffreyD.Ullman-IntroductiontoAutomataTheory,Languages,andComputation(2ndEdition) MichaelSipser.IntroductiontotheTheoryofComputation.PWSPublishing.1997.ISBN0-534-94728-X. PartOne:AutomataandLanguages,chapters1–2,pp.29–122.Section4.1:DecidableLanguages,pp.152–159.Section5.1:UndecidableProblemsfromLanguageTheory,pp.172–183. 閱論編自動機理論：形式語言和形式文法 喬姆斯基層級 文法 語言 極小自動機 類型0 無限制 遞迴可列舉 圖靈機 — (無公用名) 可判定 判定器 類型1 上下文有關 上下文有關 線性有界 — 附標 附標 巢狀堆疊 — Linearcontext-freerewritingsystemsetc. 上下文有關文法 Threadautomata — 樹-鄰接 適度上下文有關 嵌入下推 類型2 上下文無關 上下文無關 非確定下推 — 確定上下文無關 確定上下文無關 確定下推 — Visiblypushdown Visiblypushdown Visiblypushdown 類型3 正則 正則 有限 — — Star-free Counter-free(withaperiodicfinitemonoid) 每個語言範疇都是其直接上面的範疇的真子集每個語言範疇內的語言都可以用同一行的文法和自動機表示 閱論編電腦科學的主要領域註：該模板大致遵循ACM電腦分類系統(2012)（英語：ACMComputingClassificationSystem）。

電腦硬體 印刷電路板 外部裝置 積體電路 超大規模積體電路 綠色計算 電子設計自動化 系統架構組織 電腦系統架構 嵌入式系統 即時計算 網路 網路傳輸協定 路由 網路拓撲 網路服務 軟體組織 直譯器 中介軟體 虛擬機器 作業系統 軟體品質 軟體符號和工具 程式設計範式 程式語言 編譯器 領域特定語言 軟體框架 整合式開發環境 軟體組態管理 函式庫 軟體開發 軟體開發過程 需求分析 軟體設計 軟體部署 軟體維護 開源模式 計算理論 自動機 可計算性理論 計算複雜性理論 量子計算 數值計算方法 電腦邏輯 形式語意學 演算法 演算法分析 演算法設計 演算法效率（英語：Algorithmicefficiency） 隨機化演算法 計算幾何 計算數學 離散數學 資訊與計算科學 統計學 數學軟體 數理邏輯 集合論 數論 圖論 類型論 範疇論 資訊理論 數值分析 數學分析 資訊系統 資料庫管理系統 電腦數據 企業資訊系統（英語：Enterpriseinformationsystem） 社會性軟體 地理資訊系統 決策支援系統 過程控制 資料探勘 數位圖書館 系統平台 數位行銷 全球資訊網 資訊檢索 安全 密碼學 形式化方法 入侵檢測系統 網路安全 資訊安全 人機互動 電腦輔助功能 使用者介面 可穿戴電腦 普適計算 虛擬實境 聊天機器人 並行性 並行計算 平行計算 分散式計算 多執行緒 多元處理 人工智慧 自動推理 計算語言學 電腦視覺 進化計算 專家系統 自然語言處理 機器人學 機器學習 監督式學習 無監督學習 強化學習 交叉驗證 電腦圖學 電腦動畫 視覺化 彩現 修飾相片 圖形處理器 混合實境 虛擬實境 圖像處理 圖像壓縮 實體造型 應用計算 電子商務 企業級軟體 計算數學 計算物理學 計算化學 計算生物學 計算社會科學 醫學資訊學 數字藝術 電子出版 網路戰 電子遊戲 文書處理器 運籌學 教育技術學 生物資訊學 認知科學 檔案管理系統（英語：Documentmanagementsystem） 分類 主題 專題 維基共享 規範控制 BNF:cb119395737(data) FAST:1004846 GND:4003953-5 LCCN:sh85079341 NDL:00568995 取自「https://zh.wikipedia.org/w/index.php?title=自動機理論&oldid=65601663」 分類：​自動機形式語言計算模型計算機科學理論計算機科學隱藏分類：​包含BNF標識符的維基百科條目包含FAST標識符的維基百科條目包含GND標識符的維基百科條目包含LCCN標識符的維基百科條目包含NDL標識符的維基百科條目使用ISBN魔術連結的頁面 導覽選單 個人工具 沒有登入討論貢獻建立帳號登入 命名空間 條目討論 臺灣正體 不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體 查看 閱讀編輯檢視歷史 更多 搜尋 導航 首頁分類索引特色內容新聞動態近期變更隨機條目資助維基百科 說明 說明維基社群方針與指引互助客棧知識問答字詞轉換IRC即時聊天聯絡我們關於維基百科 工具 連結至此的頁面相關變更上傳檔案特殊頁面靜態連結頁面資訊引用此頁面維基數據項目 列印/匯出 下載為PDF可列印版 其他專案 維基共享資源 其他語言 العربيةBosanskiCatalàČeštinaDeutschΕλληνικάEnglishEspañolفارسیSuomiFrançaisעבריתहिन्दीHrvatskiBahasaIndonesia日本語Қазақша한국어МакедонскиMirandésNorsknynorskNorskbokmålPolskiPortuguêsRomânăРусскийSrpskohrvatski/српскохрватскиSimpleEnglishSlovenčinaСрпски/srpskiSvenskaТоҷикӣไทยTagalogTürkçeУкраїнськаTiếngViệt粵語 編輯連結