有窮自動機

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

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

identifier = letter ( letter | digit ) *

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

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

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