資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究有限自動機的不同型別有哪些？
有限自動機是一種抽象的計算裝置。它是具有離散輸入、輸出、狀態和狀態之間轉換集的系統的數學模型，這些轉換髮生在來自字母表Σ的輸入符號上。
有限自動機的形式化定義
有限自動機定義為一個五元組
M=(Q, Σ, δ,q0,F)
其中：
- Q：稱為狀態的有限集合。
- Σ：稱為字母表的有限集合。
- δ：Q × Σ → Q 是狀態轉移函式。
- q0 ∈ Q 是起始狀態或初始狀態。
- F：最終狀態或接受狀態。
型別
有限自動機的不同型別如下：
- 無輸出的有限自動機
- 確定性有限自動機 (DFA)。
- 非確定性有限自動機 (NFA 或 NDFA)。
- 具有ε-轉移的非確定性有限自動機 (ε-NFA 或 ε-NDFA)。
- 有輸出的有限自動機
- Moore 機。
- Mealy 機。
不同自動機（DFA）的定義
確定性有限自動機定義為一個五元組
M=(Q, Σ, δ,q0,F)
其中：
- Q：稱為狀態的有限集合。
- Σ：稱為字母表的有限集合。
- δ：Q × Σ → Q 是狀態轉移函式。
- q0 ∈ Q 是起始狀態或初始狀態。
- F：最終狀態或接受狀態。
非確定性有限自動機 (NFA)
NFA 也具有與 DFA 相同的五個狀態，但狀態轉移函式不同，如下所示：
δ: Q × Σ → 2Q
非確定性有限自動機定義為一個五元組：
M=(Q, Σ, δ,q0,F)
其中：
- Q：狀態的有限集合
- Σ：輸入符號的有限集合
- q0：初始狀態
- F：最終狀態
- δ：狀態轉移函式：Q × Σ → 2Q
Mealy 機
Mealy 機由六元組 (Q, q0, Σ, O, δ, λ') 描述
其中：
- Q：狀態的有限集合
- q0：機器的初始狀態
- Σ：輸入字母表的有限集合
- O：輸出字母表
- δ：狀態轉移函式，其中 Q × Σ → Q
- λ'：輸出函式，其中 Q × Σ → O
Moore 機
Moore 機由六元組 (Q, q0, Σ, O, δ, λ) 描述
其中：
- Q：狀態的有限集合
- q0：機器的初始狀態
- Σ：輸入符號的有限集合
- O：輸出字母表
- δ：狀態轉移函式，其中 Q × Σ → Q
- λ：輸出函式，其中 Q → O
更新於：2021年6月11日
13K+ 次瀏覽
廣告