什麼是理論計算機科學中的有限狀態機？

有限狀態機具有一組狀態和兩個稱為下一狀態和輸出函式的函式。

• 狀態集對應於內部儲存的所有可能組合。如果存在 n 位儲存，則存在 2n 種可能的狀態。
• 下一狀態函式是一個組合邏輯函式，它根據輸入和當前狀態確定系統的下一狀態。

下圖解釋了理論計算機科學中有限狀態機的功能。

輸出函式根據當前狀態和輸入生成一組輸出。

型別

有限狀態機的兩種型別為：

• Moore 機 - 在 Moore 機中，輸出僅取決於當前狀態。
• Mealy 機 - 在 Mealy 機中，輸出取決於當前狀態和當前輸入。

我們主要處理 Moore 機。這兩種型別在功能上是等價的。

有限狀態機包含以下內容：

• K 個狀態：S = {s1, s2, ... ,sk}，s1 是初始狀態
• N 個輸入：I = {h, i2, ... ,in}
• M 個輸出：O = {o1, o2, . ,om}
• 下一狀態函式 T(S, I)：用於將每個當前狀態和輸入對映到下一個狀態。
• 輸出函式 P(S)：此函式指定輸出。

元件

有限狀態機中存在的元件解釋如下：

狀態 - 狀態通常用圓圈繪製，並且一次只能啟用一個狀態。

表示如下：

初始狀態 - 它是我們系統的起點。初始狀態通常用指向狀態的箭頭繪製，如下所示：

最終狀態 - 它是我們已知狀態的子集，指示我們處理的輸入是否有效。接受狀態通常繪製為雙圓圈，如下所示：

轉換 - 機器從一個狀態轉換到另一個狀態，並表示為轉換。這些以兩條狀態用線連線的方式繪製，如下所示：

Bhanu Priya

更新於： 2021年6月11日

8K+ 次瀏覽

啟動你的 職業生涯

透過完成課程獲得認證

開始學習