有窮自動(dòng)機(jī)
作用：將輸入的序列轉(zhuǎn)換成一個(gè)狀態(tài)圖，方便之后的處理。通常被用在詞法分析器中。
1）有窮自動(dòng)機(jī)是一個(gè)識(shí)別器，對(duì)每個(gè)可能的的輸入串簡(jiǎn)單的回答“是”或“否”。
2）有窮自動(dòng)機(jī)分為兩類：
a)不確定的有窮自動(dòng)機(jī)（NFA）對(duì)其邊上的標(biāo)號(hào)沒有任何限制。一個(gè)符號(hào)標(biāo)記離開同一狀態(tài)的多條變，并且空串ε也可以作為標(biāo)號(hào)。
b)確定的有窮自動(dòng)機(jī)（DFA）有且只有一條離開該狀態(tài)，以該符號(hào)位標(biāo)號(hào)的邊。
不確定的有窮自動(dòng)機(jī)
定義
正則式轉(zhuǎn)NFA
這里看一個(gè)示例，下圖為正則表達(dá)式 (a | b) * abb轉(zhuǎn)換為NFA
不懂正則表達(dá)式的同學(xué)可以看這里
然后我們來具體看看是正則式怎么完成這個(gè)轉(zhuǎn)換的：
先一起來看幾個(gè)簡(jiǎn)單的小例子，應(yīng)該就懂了。
看到這，基本就懂了NFA的構(gòu)建了。其實(shí)并不難，很簡(jiǎn)單。
這里再提一點(diǎn)，拋磚引玉一下，就是對(duì)于計(jì)算機(jī)來講，構(gòu)建NFA時(shí)通常采用的是自底向上的組合法，而人的邏輯通常是自頂向下的分解法。略微有些差異，感興趣的同學(xué)可以研究討論一下這一點(diǎn)，這里不做過多的提及。
做完轉(zhuǎn)換圖后，我們還是要把他變成一個(gè)表，因?yàn)橹挥凶兂梢粋€(gè)表，才能有效的將數(shù)據(jù)錄入的計(jì)算機(jī)內(nèi)進(jìn)行運(yùn)算與處理。還是用之前的例子吧。
找出所有可以被匹配的字符即符號(hào)集合∑作為每一列的字段名，然后從起始態(tài)開始
1）狀態(tài)0可以匹配a，匹配后可以到狀態(tài)0或狀態(tài)1，記為?。匹配b只能得到狀態(tài)0，記為{0}。
2）狀態(tài)1可以匹配a，沒有匹配到，記為?。匹配b得到狀態(tài)2，記為{2}。
3）狀態(tài)0可以匹配a，沒有匹配到，記為?。匹配b得到狀態(tài)3，記為{3}。
4）狀態(tài)0可以匹配a，沒有匹配到，記為?。匹配b沒有匹配到，記為?。
至此，狀態(tài)表建立完成。正則式（RE）轉(zhuǎn)不確定型有窮自動(dòng)機(jī)（NFA）完成。
