自動機_百度百科

自動機是有限狀態機(FSM)的數學模型。

... FSM 是給定符號輸入，依據(可表達為一個表格的)轉移函數“跳轉”過一系列狀態的一種機器。

在常見的FSM 的“Mealy”變體中，這個轉移 ... 反饋 分享 複製鏈接 請複製以下鏈接發送給好友 https://baike.baidu.hk/item/自動機/7444872 複製 複製成功 自動機 編輯 鎖定 計算機控制系統的控制程序具有有限狀態自動機（FA）的特徵，可以用有限狀態機理論來描述。

有限自動機（FiniteAutomataMachine）是計算機科學的重要基石，它在軟件開發領域內通常被稱作有限狀態機（FiniteStateMachine），是一種應用非常廣泛的軟件設計模式。

中文名 自動機 外文名 automata 定    義 是有限狀態機(FSM)的數學模型 應用範圍 廣泛應用於工業生產上 重要特點 能與外界交換信息，並改變動作 重要區別 在於自動機具有固定的內在狀態 目錄 1 簡介 2 形式描述 3 術語 4 形式描述 5 分類 6 擴展 ▪ PDA ▪ LBA ▪ 圖靈機 7 能力判定 8 注意事項 自動機簡介 編輯 自動機是有限狀態機(FSM)的數學模型。

[1]  FSM是給定符號輸入，依據(可表達為一個表格的)轉移函數“跳轉”過一系列狀態的一種機器。

在常見的FSM的“Mealy”變體中，這個轉移函數告訴自動機給定當前狀態和當前字符的時候下一個狀態是什麼。

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

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

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

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

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

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

自動機automaton原來是模仿人和動物的行動而做成的機器人的意思。

但是現已被抽象化為如下的機器。

時間是離散的（t=0，1，2……），在每一個時刻它處於所存在的有限個內部狀態中的一個。

對每一個時刻給予有限個輸入中的一個。

那麼下一個時刻的內部狀態就由現在的輸入和現在的內部狀態所決定。

每個時刻的輸出只由那個時刻的內部狀態所決定。

作為自動機的例子可以舉出由McCulloch-pitts的神經模型組合所得到的神經網絡模型、數字計算機等。

自動機形式描述 編輯 對信號序列進行邏輯處理的裝置。

在自動控制領域內，是指離散數字系統的動態數學模型，可定義為一種邏輯結構，一種算法或一種符號串變換。

自動機這一術語也廣泛出現在許多其他相關的學科中，分別有不同的內容和研究目標。

在計算機科學中自動機用作計算機和計算過程的動態數學模型，用來研究計算機的體系結構、邏輯操作、程序設計乃至計算複雜性理論。

在語言學中則把自動機作為語言識別器，用來研究各種形式語言。

[2]  在神經生理學中把自動機定義為神經網絡的動態模型，用來研究神經生理活動和思維規律，探索人腦的機制。

在生物學中有人把自動機作為生命體的生長髮育模型，研究新陳代謝和遺傳變異。

在數學中則用自動機定義可計算函數，研究各種算法。

現代自動機的一個重要特點是能與外界交換信息，並根據交換得來的信息改變自己的動作，即改變自己的功能，甚至改變自己的結構，以適應外界的變化。

也就是説在一定程度上具有類似於生命有機體那樣的適應環境變化的能力。

自動機與一般機器的重要區別在於自動機具有固定的內在狀態，即具有記憶能力和識別判斷能力或決策能力，這正是現代信息處理系統的共同特點。

因此，自動機適宜於作為信息處理系統乃至一切信息系統的數學模型。

自動機可按其變量集和函數的特性分類，也可按其抽象結構和聯結方式分類。

主要有：有限自動機和無限自動機、線性自動機和非線性自動機、確定型自動機和不確定型自動機、同步自動機和異步自動機、級聯自動機和細胞自動機等。

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

符號有時就叫做“字母”。

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

字母表符號的有限集合。

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

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

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

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

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

形式上説，所有可能字符串的集合叫做自由幺半羣。

它被指示為Σ，上標*被稱為Kleene星號。

自動機形式描述 編輯 自動機可以表示為5-元組，這裏的:Q是狀態的非空有窮集合。

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

輸入字符串都是∑上的字符串 δ是狀態轉移函數，就是（右2）。

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

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

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

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

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

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

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

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

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

從一個狀態q通過這種方法可到達的狀態的集合叫做q的ε-閉包。

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

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

自動機擴展 編輯 上述自動機接受的語言家族被稱為正規語言(RegularExpression)。

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

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

轉移函數δ也依賴於在棧頂的符號，並在每次轉移時指定如何變更棧。

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

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

LBA接受上下文有關語言。

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

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

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

圖靈機判定遞歸語言並識別遞歸可枚舉語言。

自動機能力判定 編輯 確定有限狀態自動機與非確定有限狀態自動機識別的語言都是正則語言。

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

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

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

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

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

自動機注意事項 編輯 注意，自動機一般不必須有有限數目甚至可數個狀態。

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

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

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

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

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

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

自動機廣泛應用於工業生產上。

參考資料 1.    有限狀態機及其應用  ．知網[引用日期2017-04-10] 2.    一種形式語言代數模型  ．知網[引用日期2017-04-10] 3.    圖靈機及其構造研究  ．知網[引用日期2017-04-10] 4.    基於有限狀態自動機的服務組合模型  ．知網[引用日期2017-04-10] 圖集 自動機的概述圖（1張） 詞條統計 瀏覽次數：次 編輯次數：34次歷史版本 最近更新： 早晨的阳光755 （2021-12-11） 1 簡介 2 形式描述 3 術語 4 形式描述 5 分類 6 擴展 6.1 PDA 6.2 LBA 6.3 圖靈機 7 能力判定 8 注意事項 百科協議    隱私協議    意見反饋 Beta 進入詞條 清除歷史記錄關閉 編輯 反饋 登錄