正則表達(dá)式所使用的理論模型就是有窮自動(dòng)機(jī)慎冤，其具體實(shí)現(xiàn)稱為正則引擎（regex engine）严望。用正則表達(dá)式處理字符串村象，首先需要生成自動(dòng)機(jī)（“編譯”正則對(duì)象）亭病；之后無(wú)論輸入什么字符串鹅很，正則引擎都只需要老老實(shí)實(shí)地在狀態(tài)之間游走。
圖8-2顯示了正則表達(dá)式a(bb)+a對(duì)應(yīng)的自動(dòng)機(jī)罪帖。
[圖片上傳失敗...(image-cd0daa-1545311176685)]
在這臺(tái)有窮自動(dòng)機(jī)中促煮，s0、s1…整袁、s4是各個(gè)狀態(tài)菠齿，s0為開始狀態(tài)，s4為最終狀態(tài)坐昙；轉(zhuǎn)移函數(shù)很直觀：比如當(dāng)前狀態(tài)是s0绳匀，輸入字符a，則轉(zhuǎn)移到s1炸客；如果當(dāng)前狀態(tài)s0疾棵，輸入的不是a，則直接退出痹仙。這也很好理解：該正則表達(dá)式只能匹配以a開頭的字符串是尔，否則不匹配。
圖8-3說(shuō)明了這臺(tái)有窮自動(dòng)機(jī)對(duì)字符串a(chǎn)bbbba的處理過程开仰。
[圖片上傳失敗...(image-d8d5d3-1545311176685)]
在經(jīng)歷了一系列對(duì)狀態(tài)轉(zhuǎn)移之后拟枚，字符串a(chǎn)bbbba處理完畢，自動(dòng)機(jī)停留在最終狀態(tài)上抖所，也就是說(shuō)梨州，字符串abbbba可以由正則表達(dá)式a(bb)+a匹配。
同一個(gè)正則表達(dá)式對(duì)應(yīng)的有窮自動(dòng)機(jī)不止一臺(tái)田轧，可能是若干臺(tái)暴匠，這些有窮自動(dòng)機(jī)是等價(jià)的。同樣是a(bb)+a傻粘，它可以對(duì)應(yīng)到如下對(duì)兩臺(tái)完全等價(jià)對(duì)有窮自動(dòng)機(jī)每窖。
[圖片上傳失敗...(image-9e26f2-1545311176685)]
仔細(xì)觀察發(fā)現(xiàn)，第二臺(tái)自動(dòng)機(jī)有些奇怪弦悉，在輸入ab之后窒典，再輸入b，它所處第狀態(tài)是不確定的：可能在s1稽莉，也可能在s3瀑志。但是輸入a(bb)+a能匹配的字符串，它確實(shí)可以抵達(dá)最總狀態(tài)s4.
圖8-5所示的自動(dòng)機(jī)看起來(lái)更加奇怪，但它仍于a(bb)+a是完全對(duì)應(yīng)的劈猪。
[圖片上傳失敗...(image-4ae298-1545311176685)]
在狀態(tài)s3昧甘，即便沒有輸入任何字符，也不會(huì)停下來(lái)战得，而是憑空轉(zhuǎn)義到s1充边。也就是說(shuō)，在某個(gè)時(shí)刻常侦，自動(dòng)機(jī)到底處于s3還是s1浇冰，這時(shí)不確定的！但是對(duì)于這種不確定性聋亡，并不會(huì)影響自動(dòng)機(jī)對(duì)于正則表達(dá)式a(bb)+a到匹配肘习。也就是說(shuō)，這臺(tái)自動(dòng)機(jī)與之前的兩臺(tái)自動(dòng)機(jī)是完全等價(jià)的杀捻。
根據(jù)狀態(tài)的確定與否井厌，一般我們會(huì)把有窮自動(dòng)機(jī)（正則引擎）分為兩類：一類是確定型有窮自動(dòng)機(jī)（definite finite automata蚓庭，簡(jiǎn)稱DFA）致讥，在任何時(shí)刻，它所處的狀態(tài)是確定無(wú)疑的器赞；另一臺(tái)是非確定型有窮自動(dòng)機(jī)（non-definite finite automata垢袱，簡(jiǎn)稱NFA），在某個(gè)時(shí)刻港柜，它所處的狀態(tài)可能是不確定的请契。
圖8-6把上面的三臺(tái)自動(dòng)機(jī)做了分類，第一臺(tái)是DFA夏醉，另兩臺(tái)是NFA爽锥。
[圖片上傳失敗...(image-c82872-1545311176685)]
可以證明，DFA和NFA之間存在等價(jià)關(guān)系：也就是說(shuō)畔柔，每一臺(tái)DFA都可以等價(jià)轉(zhuǎn)換為一臺(tái)NFA氯夷，反過來(lái)也成立（具體證明過程很復(fù)雜，這里略去靶擦，有興趣可自行查閱計(jì)算理論相關(guān)資料）腮考。
比較正則表達(dá)式a(bb)+a和這三臺(tái)自動(dòng)機(jī)，會(huì)發(fā)現(xiàn)NFA構(gòu)造起來(lái)更直觀玄捕，實(shí)際上這是普遍規(guī)律：從正則表達(dá)式出發(fā)踩蔚，構(gòu)造NFA的難度要小于DFA。但是正如之前說(shuō)的枚粘，DFA在任意時(shí)刻必定處于某個(gè)確定的狀態(tài)馅闽，而NFA可能處于若干狀態(tài)之中的一個(gè)，所以，如果使用NFA福也，就必須保存所有可能的狀態(tài)孝冒，并且在某種狀態(tài)不可行時(shí)“回退”到之前保存的狀態(tài)，這就是正則表達(dá)式匹配中的重要概念：回溯拟杉。
