上篇我們介紹了詞法分析階段單詞的識別工具--正規式。本篇介紹正規式的識別裝置--有窮自動機。
之所以稱為有窮自動機？我想這和人們把把不同的設計模式起了名字一樣，和同樣是java代碼被稱為Servlet一樣。人們把抽象的東西起了一個客觀的名字。
**有窮自動機：**
能準確的識別正規集，能識別正規文法所定義的語言和正規式表示的集合，也為詞法分析程序的自動構造尋找特殊的方法和工具。
分為兩類：**確定的有窮自動機**（determinirstic finite automata）和**不確定的有窮自動機**(nondeterministic finite automata)。
確定和不確定的區別在哪里呢？首先分別看看我們的定義。
**確定有窮自動機：**
一個確定的有窮自動機M是一個五元組：M=（K，?∑，f，S，Z）其中，
1)K是一個有窮集，他的每個元素稱為一種狀態。
2）?∑是一個有窮字母表，他的每個元素稱為一個輸入符號，所以∑稱為輸入符號表。
3）f是轉換函數，是KX∑-->K 上的映像，例如f（ki，a）=kj這就意味著，當前狀態為k，輸入字符a后，將轉換到下一狀態kj，我們把kj稱為ki的一個后繼狀態；
4）S屬于K，是**唯一**的一個出態。
5）Z屬于K，是一個終態，終態也稱為可接受狀態或結束狀態。
例 如下：
一個DFA可以表示一個狀態轉換圖，如下所示：
也可以用狀態矩陣顯示，行表示狀態，列表示輸入符號，終態在表的右端標1，非終態在表的右邊標0。
**不確定有窮自動機：**
與確定有窮自動機不同：
3）是一個子集映像。
4）S屬于K是一個非空出態集；
5）Z屬于K是一個終態集。
例如：
注:?上面的圖片中改為 f（0，b）={0}
他們有什么不同之處呢？
1）確定有窮自動機狀態是唯一的。
2）確定有窮自動機f是單值映射。
確定的有窮自動機就是說當一個狀態面對一個輸入符號的時候，它所轉換到的是一個唯一確定的狀態；而不確定的有窮自動機是說當一個狀態面對一個輸入符號的時候，它所轉換到的可能不只一個狀態，可以是一個狀態集合。這就是兩者的主要區別。還有就是DFA的開始狀態是唯一的，而NFA的開始狀態是一個開始狀態集。
我們自己理解，確定和不確定的區別，確定是不怎么變化的，不確定是變化的，無論是變化還是不變化的問題的本質呢？
本篇就介紹到這里，下篇介紹不確定有窮自動機和確定有窮自動機之間的轉換和自動機的最小化。
愿開心閱讀~~~
?????????
??????????
????????
??????
