資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究解釋構造最小有限狀態自動機的 方法。
有限狀態機 (FSM) 有一組狀態和兩個稱為下一狀態和輸出函式的函式。
狀態集對應於內部儲存的所有可能組合。
如果有 n 位儲存，則有 2n 個可能的狀態。
下一狀態函式是一個組合邏輯函式，它根據輸入和當前狀態確定系統的下一狀態。
有限狀態機由以下部分組成：
- K 個狀態：S = {s1, s2, ... ,sk}，s1 是初始狀態
- N 個輸入：I = {h, i2, ... ,in}
- M 個輸出：O = {o1, o2, . ,om}
下一狀態函式 T(S, I) 用於對映每個當前狀態並給出輸入到下一狀態。輸出函式 P(S) 指定輸出。
FSM 的最小化意味著減少給定 FA 的狀態數。因此，在最小化 FSM 後，我們得到了具有冗餘狀態的 FSM。
在最小化 FSM 時，我們首先找出哪些兩個狀態是等價的。如果兩個狀態是等價的，那麼我們可以用一個代表狀態來表示這兩個狀態。
如果對於所有 x ∈ Σ*（Σ* 表示任意長度的任意字串），δ(q1,x) 和 δ(q2,x) 都是最終狀態或它們都是非最終狀態，則兩個狀態 q1 和 q2 是等價的。
我們可以透過查詢等價狀態來最小化給定的 FSM。
方法
構造最小有限狀態自動機的方法如下所述：
**步驟 1** - 建立一個集合 S0 作為 S0={Q01, Q02}，其中 Q01 是所有最終狀態的集合，而 Q02 = Q-Q01，其中 Q 是 DFA 中所有狀態的集合。
**步驟 2** - 從 Sk 構造 Sk+1。
令 Qik 為 S0 中的任何子集。如果 q1 和 q2 在 Qik 中，則如果 δ(q1,a) 和 δ(q2,a) 是 K 等價的，則它們是 (k+1) 等價的。找出 δ(q1,a) 和 δ(q2,a) 是否駐留在同一個等價類 δ0 中。
然後，據說 q1 和 q2 是 (k+1) 等價的。因此，Qik 進一步劃分為 (k+1) 個等價類。
**步驟 3** - 對 Sk 中的每個 Qik 重複步驟 2，並獲得 Sk+1 的所有元素。
**步驟 4** - 為 n=1,2,3,…..構造 Sn，直到 Sn=Sn+1。
**步驟 5** - 然後，用代表狀態替換一個等價類中的所有等價狀態。
2K+ 次檢視
