非確定有限狀態(tài)機(jī)
我們可以將KMP算法看做一臺(tái)由模式字符串構(gòu)造的能夠掃描文本的有限狀態(tài)自動(dòng)機(jī)焊刹，而對(duì)于正則表達(dá)式我們要將這個(gè)思想推廣擎值。
KMP的有限狀態(tài)自動(dòng)機(jī)會(huì)根據(jù)文本中的字符改變自身的狀態(tài)。當(dāng)且僅當(dāng)自動(dòng)機(jī)達(dá)到停止?fàn)顟B(tài)時(shí)它才找到了一個(gè)匹配眉抬。算法本身就是模擬這種自動(dòng)機(jī)儡嘶，這種自動(dòng)機(jī)運(yùn)行很容易模擬的原因是因?yàn)樗谴_定的：每種狀態(tài)的轉(zhuǎn)換都完全由文本中的字符所決定张峰。
要處理正則表達(dá)式，就需要一種更加強(qiáng)大的抽象狀態(tài)機(jī)堪簿。因?yàn)榛虿僮鞯拇嬖谌詣?dòng)機(jī)無(wú)法僅根據(jù)一個(gè)字符就判斷模式是否出現(xiàn)；事實(shí)上椭更，因?yàn)殚]包的存在哪审，自動(dòng)機(jī)甚至無(wú)法知道檢查多少個(gè)字符才會(huì)匹配失效。為了克服這些困難虑瀑，我們需要非確定性的自動(dòng)機(jī)：當(dāng)面對(duì)匹配模式的多種可能時(shí)，自動(dòng)機(jī)能夠“猜出”正確的轉(zhuǎn)換，也就是所謂的非確定有限狀態(tài)自動(dòng)機(jī)（NFA）虐骑。
Kleene定理是理論計(jì)算機(jī)科學(xué)中的一個(gè)重要結(jié)論俱两，它證明了對(duì)于任意正則表達(dá)式都存在一個(gè)與之對(duì)應(yīng)的非確定有限狀態(tài)機(jī)（反之亦然）。
NFA中從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)規(guī)則與DFA有所不同：
- 如果當(dāng)前狀態(tài)和字母表中的一個(gè)字符相對(duì)應(yīng)且文本中的當(dāng)前字符和該字符相匹配痛侍，自動(dòng)機(jī)可以燒過(guò)文本中的該字符并轉(zhuǎn)換到下一個(gè)狀態(tài)（匹配轉(zhuǎn)換朝氓，具有唯一性）。
- 自動(dòng)機(jī)可以通過(guò)紅色的邊轉(zhuǎn)換到另一個(gè)狀態(tài)而不掃描文本中的任何字符（可以轉(zhuǎn)換至多種狀態(tài)）恋日。
以上充分說(shuō)明了NFA和DFA之間的關(guān)鍵區(qū)別膀篮，NFA離開(kāi)一個(gè)狀態(tài)的轉(zhuǎn)換有多種，因此從這種狀態(tài)可能進(jìn)行的轉(zhuǎn)換是不確定的岂膳。但和DFA一樣誓竿，列出所有狀態(tài)的轉(zhuǎn)換即可追蹤NFA處理文本字符串的軌跡，而找到這一序列的方法就是系統(tǒng)的嘗試所有的可能性谈截。
判定一個(gè)長(zhǎng)度為M的正則表達(dá)式所對(duì)應(yīng)的NFA能否識(shí)別一段長(zhǎng)度為N的文本所需的時(shí)間在最壞的情況下和MN成正比筷屡。
public boolean recognizes(String txt){
Bag<Integer> pc = new Bag<Integer>();
Directed dfs = new DirectedDFS(G,0);
for(int v = 0; v<G.V(); v++)
if(dfs.marked(v)) pc.add(v);
for(int i = 0; i<txt.length(); i++){
Bag<Integer> match = new Bag<Integer>();
for(int v: pc)
if( v<M)
if(re[v] == txt.charAt(i) || re[v] == ".")
match.add(v+1）；
pc = new Bag<integer>();
dfs = new DirectedDFS(G,match);
for(int v=0; v<G.V(); v++)
if(dfs.marked(v)) pc.add(v);
}
for(int v: pc) if(v==M) return true;
return false;
}
將正則表達(dá)式轉(zhuǎn)化為NFA的過(guò)程在某種程度上類(lèi)似于之前所說(shuō)過(guò)的Dijkstra的雙棧算法對(duì)表達(dá)式求值簸喂。
public class NFA{
private char[] re;
private Digraph G;
private int M;
public NFA(String regexp){
Stack<Integer> ops = new Stack<Integer>();
re = regexp.toCharArray();
M = re.length;
G = new Digraph(M+1);
for(int i=0; i<M; i++){
int lp = i;
if(re[i] == '(' || re[i] == '|')
ops.push(i);
else if(re[i] == ')'){
int or = ops.pop();
if(re[or] == '|'){
lp = ops.pop();
G.addEdge(lp, or+1);
G.addEdge(or, i);
}
else lp = or;
}
if( i<M-1 && re[i+1] == '*'){
G.addEdge(lp, i+1);
G.addEdge(i+1, lp);
}
if(re[i] == '(' || re[i] == '*' || re[i] == ')')
G.addEdge(i, i+1);
}
}
public boolean recognizes(String txt)
}