有窮自動機

有窮自動機，或有窮狀態的機器，是描述（或“機器”）特定類型算法的數學方法。特別地，有窮自動機可用作描述在輸入串中識別模式的過程，因此也能用作構造掃描程式。

基本介紹

• 中文名：有窮自動機
• 定義：描述特定類型算法的數學方法
• 分類：確定型，非確定型
• 學科：編譯原理

當然有窮自動機與正則表達式之間有著很密切的關係，在下一節中大家將會看到如何從正則表達式中構造有窮自動機。但在學習有窮自動機之前，先看一個說明的示例。

通過下面的正則表達式可在程式設計語言中給出標識符模式的一般定義（假設已定義了letter 和digit）：

identifier = letter ( letter | digit ) *

它代表以一個字母開頭且其後為任意字母和/ 或數字序列的串。

　通過標明數字1 和2 的圓圈表示的是狀態（state），它們表示其中記錄已被發現的模式的數量在識別過程中的位置。帶有箭頭的線代表由記錄一個狀態向另一個狀態的轉換（transition），該轉換依賴於所標字元的匹配。

有窮自動機

有窮自動機又分為確定型的有窮自動機（DFA）與非確定型的有窮自動機（NFA）兩種。