|
|
對信號序列進行邏 輯 處理的裝 置。在自動控製領域內，是指離散數字係統的動態數學模型，可定義為一種邏輯結構，一種算法或一種符號串變換。自動機這一術語也廣泛出現在許多其他相關的學科中，分別有不同的內容和研究目標。在計算機科學中自動機用作計算機和計算過程的動態數學模型，用來研究計算機的體係結構、邏輯操作、程序設計乃至計算復雜性理論。在語言學中則把自動機作為語言識別器，用來研究各種形式語言。在神經生理學中把自動機定義為神經網絡的動態模型，用來研究神經生理活動和思維規律，探索人腦的機製。在生物學中有人把自動機作為生命體的生長發育模型，研究新陳代謝和遺傳變異。在數學中則用自動機定義可計算函數，研究各種算法。現代自動機的一個重要特點是能與外界交換信息，並根據交換得來的信息改變自己的動作，即改變自己的功能，甚至改變自己的結構，以適應外界的變化。也就是說在一定程度上具有類似於生命有機體那樣的適應環境變化的能力。
自動機與一般機器的重要區別在於自動機具有固定的內在狀態，即具有記憶能力和識別判斷能力或决策能力，這正是現代信息處理係統的共同特點。因此，自動機適宜於作為信息處理係統乃至一切信息係統的數學模型。自動機可按其變量集和函數的特性分類，也可按其抽象結構和聯結方式分類。主要有：有限自動機和無限自動機、綫性自動機和非綫性自動機、確定型自動機和不確定型自動機、同步自動機和異步自動機、級聯自動機和細胞自動機等。 |
|
下面是三類有限自動機
確定有限自動機(DFA)
自動機的每個狀態都有對字母表中所有符號的轉移。
非確定有限自動機(NFA)
自動機的狀態對字母表中的每個符號可以有也可以沒有轉移，對一個符號甚至可以有多個轉移。自動機接受一個字，如果存在至少一個從 q0 到 F 中標記(label)著這個輸入字的一個狀態的路徑。如果一個轉移是「未定義」的，自動機因此不知道如何繼續讀取輸入，則拒絶這個字。
有ε轉移的非確定有限自動機(FND-ε或ε-NFA)
除了有能力對任何符號跳轉到更多狀態或沒有狀態可以跳轉之外，它們可以做根本不關於符號的跳轉。就是說，如果一個狀態有標記著 ε 的轉移，則 NFA 可以處在 ε-轉移可到達的任何狀態中，直接或通過其他有 ε-轉移的狀態。從一個狀態 q 通過這種方法可到達的狀態的集合叫做 q 的 ε-閉包。
儘管可以證明所有這些自動機都「可以接受同樣的語言」。你總是可以構造接受與給定的 NFA M 同樣語言的某個 DFA M。 |
|
上述自動機接受的語言傢族被稱為正則語言傢族。更強力的自動機可以接受更復雜的語言。比如:
下推自動機(PDA)
這種機器等同於 DFA (或 NFA)，除了它們額外的裝備了棧形式的內存。轉移函數 δ 也依賴於在棧頂的符號，並在每次轉移時指定如何變更棧。非確定 PDA 接受上下文無關語言。
綫性有界自動機(LBA)
LBA 是有限製的圖靈機；不使用無限磁帶，它的磁帶有同輸入字元串成正比的空間。LBA 接受上下文有關語言。
圖靈機
它們是最強力的電腦器。它們擁有磁帶形式的無限內存，和可以讀取和變更磁帶的磁頭，它可在磁帶上嚮任何方向移動。圖靈機等價於演算法，是現代電腦的理論基礎。圖靈機判定遞歸語言並識別遞歸可枚舉語言。 |
|
| 根據 Myhill-Nerode定理，在同構意義下接受一個正則語言的最少狀態的確定有限狀態自動機是唯一的。同時我們還存在有效的演算法（時間開銷是O(n2)的）構造出與給定確定有限狀態自動機等價的最小化的確定有限狀態自動機。 |
|
確定有限狀態自動機與非確定有限狀態自動機識別的語言都是正則語言。由於正則語言的良好性質，許多為其他自動機（下推自動機或圖靈機）不能判定的問題，在有限狀態自動機的情形下，都可以得到判定，並且存在有效的演算法。
對一個確定有限狀態自動機，下述判定問題都可以判定，並且存在有效的演算法。
該自動機識別的語言是否為空集。
該自動機識別的語言是否為有限集。
該自動機是否與另一個確定有限狀態自動機識別同一個的語言。 |
|
zidongji
自動機
automata
對信號序列進行邏輯處理的裝置。在自動機理論中主要是指抽象自動機。抽象自動機是用來表示邏輯關係的動態數學模型，一般都是指能變換和處理信息的離散係統的動態數學模型。在自動控製領域內，自動機是指離散數字係統的動態數學模型，它可定義為一種邏輯結構，一種算法或一種符號串變換。自動機這一術語也廣泛出現在許多其他相關的學科中，分別有不同的內容和研究目標。在計算機科學中自動機用作計算機和計算過程的動態數學模型，用來研究計算機的體係結構、邏輯操作、程序設計、乃至計算復雜性理論。在語言學中則把自動機作為語言識別器，用來研究各種形式語言。在神經生理學中把自動機定義為神經網絡的動態模型，用來研究神經生理活動和思維規律，探索人腦的機製。在生物學中有人把自動機作為生命體的生長發育模型，研究新陳代謝和遺傳變異。在數學中則用自動機定義可計算函數，研究各種算法。
自動機的組成和特點 自動機起源於20世紀30年代的圖靈機,一般都有以下3個組成部分：①輸入設備：又稱傳感器或變送器，相當於生命有機體的感受器，用來接受外界的信息。②輸出設備：又稱執行器，相當於生命有機體的效應器，用來嚮外界輸出信息，執行各種操作，實現信息的效用。③中央處理器：又稱調節器或控製器，相當於生命有機體的神經係統，用來處理、存儲和傳遞信息。現代自動機的一個重要特點是能與外界交換信息，並根據交換得來的信息改變自己的動作，即改變自己的功能，甚至改變自己的結構，以適應外界的變化。也就是說在一定程度上具有類似於生命有機體那樣的適應環境變化的能力。
自動機與一般機器的重要區別在於自動機具有固定的內在狀態，即具有記憶能力和識別判斷能力或决策能力，這正是現代信息處理係統的共同特點。因此，自動機適宜於作為信息處理係統乃至一切信息係統的數學模型。當自動機與環境進行信息交換時，輸出不僅决定於輸入，而且也决定於自動機的內在狀態。自動機通過內在狀態來記憶過去的輸入，新的輸入又反映在新的內在狀態中，因此內在狀態起着內存儲器的作用。自動機的這種信息變換規律表明，一個自動機可用一個五元組表示:A＝(□,□,□,□,□)。式中□、□ 和□分別是狀態集、輸入集和輸出集,□和□分別是狀態轉移函數和輸出函數,即映射 □:□×□→□和□:□×□→□。自動機的行為也可以用狀態轉移圖即狀態圖來表示 (見圖自動機□的狀態圖)。狀態圖是一種有嚮圖。用節點表示狀態，箭頭表示狀態轉移的方向，箭頭旁的字符或數字表示輸入或輸出，視箭頭對於節點的嚮背而定。A能識別 {□∈{0,1}|□ 以11結束且無連續0｝。
自動機分類 自動機可按其變量集和函數的特性分類，也可按其抽象結構和聯結方式分類。主要有以下幾類:①有限自動機和無限自動機。如果□,□,□都是有限集，則稱□為有限自動機，又稱時序機。如果□,□,□中有一個是無限集,則稱□為無限自動機。有限自動機是時序網絡和一切序儲量有限的離散係統的數學模型，如神經網絡和語言識別器等。②綫性自動機和非綫性自動機。如果□ 和□ 均是綫性函數,則稱□為綫性自動機,否則稱□為非綫性自動機。綫性自動機便於用綫性時序電路來實現,在編碼網絡、通信網絡和計算機控製係統中應用甚廣。③確定型自動機和不確定型自動機。如果自動機 A下一內在狀態可由當前的輸入和當前的內在狀態所完全决定，則稱A為確定型自動機，否則稱A為不確定型自動機。概率自動機和模糊自動機均屬於不確定型自動機。概率自動機是指自動機所處環境或其內部有隨機因素的 |
|
- : automata
- n.: automat, Automaton, automatons, robot
|
|
| 自動裝置 |
|
|
|
| 自動機器 | 自動機械 | | 自動機論 | 自動機床 | | 自動機圖 | 子自動機 | | 棧自動機 | 裝自動機器 | | 有限自動機 | 細胞自動機 | | 自動機械表 | 概率自動機 | | 元胞自動機 | 有窮自動機 | | 自動機理論 | 下推自動機 | | 極小自動機 | 連通自動機 | | 數字自動機 | 隨機自動機 | | 情景自動機 | 學習自動機 | | 智能自動機 | 計算自動機 | | 約化自動機 | 完全自動機 | | 抽象自動機 | 全自動機械表 | | 自動機的等價 | 自動機的同態 | | 自動機械機芯 | 概率自動機論 | | 自動機械水表 | 單嚮棧自動機 | | 有限態自動機 | 確定性自動機 | | 自再生自動機 | 自動機床用鋼 | | 火炮自動機設計 | 有限自動機理論 | | 水下自動機器人 | 有限狀態自動機 | | 雙嚮有窮自動機 | 綫性有界自動機 | | 不確定性自動機 | 有限存儲自動機 | | 綫性有限自動機 | 非抹除棧自動機 | | 雙帶有窮自動機 | 雙嚮下推自動機 | | 句法分析自動機 | 航空自動機關炮 | | 非决定性自動機 | 形式語言與自動機 | | 人臉自動機器識別 | 自動機理論與應用 | | 自動機的代數理論 | 自動機的半群理論 | | 全自動機械過濾器 | 確定型下推自動機 | | 確定型有窮自動機 | 有窮自動機最小化 | | 形式語言與自動機理論 | 自動機理論語言和計算導論 | | 有限狀態機有限自動機 | 有窮轉嚮下推自動機 | | 標準形式下推自動機 | 非確定型有窮自動機 | | 基於元胞自動機的交通係統建模與模擬 | 自動機理論、語言和計算機導論(英文版·第3版) | | 有限自動機及在密碼學中的應用 | 形式語言與自動機理論教學參考書 | | 自動機理論、語言和計算導論 | 自動機理論語言和計算機導論(英文版·第3版) | |
|