dfa演算法的工作原理

『壹』 ！！編譯原理DFA和NFA

DFA或NFA是對計算機程序的行為的抽象模型。你編寫的程序其實就對應了一個自動機。簡單舉例來說，如果a,b可以取值0或1; 程序： if(a==1) b=1; 這個程序對應了一個自動機。
對應的自動機就有狀態 (0,0), (0,1), (1,1), (1, 0)
比如你自動機的初始狀態是 (1,0)即a=1,b=0時，運行程序的下一個狀態就是(1,1)。

畫圖出來就是 這4個狀態作為頂點，並且有下面幾條邊
(0,0) --> (0,0)（自環）, (1,0)-->(1,1), (1,1)-->(1,1)（自環）, (0,1)-->(0,1)自環

存在的意義就是一種理論模型，也可以認為是一種編程思想。 詞法分析系也離不開 if else， 這一系列的if else和條件也就組成自動機。。。

最經典體現自動機思想的演算法就是KMP演算法，你肯定學過，字元串子串匹配的演算法。 回憶這個演算法的過程：演算法第一步構造的next表（數據結構教材的說法）其實就是根據子串的內容構造了一個自動機！ 演算法第二步將原串作為自動機輸入，自動機的輸出就是匹配到的子串位置或者無匹配。

『貳』 編譯原理NFA轉DFA ，請問DFA的初始狀態如何確定

NFA確定化的時候，包含NFA初態的那個DFA狀態就是確定後的DFA的初態。

DFA的終態就是所有包含了NFA終態的DFA的狀態。

對於DFA來說，他的初態就是包含了NFA唯一初態1的那個狀態，就是左邊的1，2右邊的1了。

脫氧核糖-磷酸鏈在螺旋結構的外面，鹼基朝向裡面。兩條多脫氧核苷酸鏈反向互補，通過鹼基間的氫鍵形成的鹼基配對相連，形成相當穩定的組合。

(2)dfa演算法的工作原理擴展閱讀：

將DNA或RNA序列以三個核苷酸為一組的密碼子轉譯為蛋白質的氨基酸序列，以用於蛋白質合成。密碼子由mRNA上的三個核苷酸（例如ACU，CAG，UUU）的序列組成，每三個核苷酸與特定氨基酸相關。

例如，三個重復的胸腺嘧啶（UUU）編碼苯丙氨酸。使用三個字母，可以擁有多達64種不同的組合。由於有64種可能的三聯體和僅20種氨基酸，因此認為遺傳密碼是多餘的（或簡並的）：一些氨基酸確實可以由幾種不同的三聯體編碼。

但每個三聯體將對應於單個氨基酸。最後，有三個三聯體不編碼任何氨基酸，它們代錶停止（或無意義）密碼子，分別是UAA，UGA和UAG 。

『叄』 編譯原理由正規式構造DFA

先畫出NFA，如圖：（我就是傳說當中的靈魂畫師）

這個DFA本身就已經是最簡的了，無法再簡化，最簡化過程我就直接省了

『肆』 DFA的最小化演算法

首先劃分終態集和非終態集，之後不斷進行劃分，直到不再發生變化。
每輪劃分對所有子集進行。對一個子集的劃分中，若每個輸入符號都能把狀態轉換到等價的狀態，則兩個狀態等價。

劃分完成後，從每個子集選出一個代表，若DFA中存在兩個子集內狀態之間的轉換，則MFA中兩個子集的代表之間也存在對應的轉換。簡便方法：對每個子集刪去除代表以外的狀態，並把指向它們的箭弧改為指向代表。
MFA的初態是含有DFA初態的子集的代表。MFA的終態集是DFA終態集劃分出來子集的代表。
最後，從MFA中刪除從初態無法到達的狀態和死狀態（只有入射弧或指向自身的出射弧的非終止狀態）。

去除不可達狀態。建表，行列為不同狀態，未標記的格子行列狀態等價。首先標記行列一個非終止狀態一個終止狀態的格子。對未標記的格子(q,q')，若存在一個輸入符號a，使q經a到達狀態和q'經a到達狀態不等價，則標記(q,q')。重復直到表格不再變化。

對於所有未標記的(q,q')，把與q'有關的轉換都改到q上，刪除q'。

『伍』 dfa演算法的關鍵點是什麼

起因: 從網頁中爬去的頁面，需要判斷是否跟預設的關鍵詞匹配(是否包含預設的關鍵詞)，並返回所有匹配到的關鍵詞 。
目前pypi 上兩個實現

但是其實包都是基於DFA 實現的
這里提供源碼如下:
#!/usr/bin/python2.6
# -*- coding: utf-8 -*-
import time
class Node(object):
def __init__(self):
self.children = None
# 標記匹配到了關鍵詞
self.flag = False

# The encode of word is UTF-8
def add_word(root,word):
if len(word) <= 0:
return
node = root
for i in range(len(word)):
if node.children == None:
node.children = {}
node.children[word[i]] = Node()

elif word[i] not in node.children:
node.children[word[i]] = Node()

node = node.children[word[i]]
node.flag = True

def init(word_list):
root = Node()
for line in word_list:
add_word(root,line)
return root

# The encode of word is UTF-8
# The encode of message is UTF-8
def key_contain(message, root):
res = set()
for i in range(len(message)):
p = root
j = i
while (j<len(message) and p.children!=None and message[j] in p.children):
if p.flag == True:
res.add(message[i:j])
p = p.children[message[j]]
j = j + 1

if p.children==None:
res.add(message[i:j])
#print '---word---',message[i:j]
return res

def dfa():
print '----------------dfa-----------'
word_list = ['hello', '民警', '朋友','女兒','派出所', '派出所民警']
root = init(word_list)

message = '四處亂咬亂吠，嚇得家中11歲的女兒躲在屋裡不敢出來，直到轄區派出所民警趕到後，才將孩子從屋中救出。最後在徵得主人同意後，民警和村民合力將這只發瘋的狗打死'
x = key_contain(message, root)
for item in x:
print item

if __name__ == '__main__':
dfa()

『陸』 如題，編譯原理中為什麼要將NFA轉化為DFA

對DFA來說，一個輸入必然對應唯一的路徑與結果，而這正是我們設計編譯器所需要的。

如果從一個狀態經過同樣的一個輸入可以通過兩條或更多路徑達到不同的狀態，我們的編譯器就會迷惑（不知道怎麼辦），只能通過窮舉測試每個狀態是否可行，而窮舉演算法的效率通常都很低下。
DFA的最簡化是有固定演算法的，NFA有沒有我不知道，通常最簡化之後的DFA要比NFA簡單得多

『柒』 基本排序演算法原理

演算法原理：每次對相鄰的兩個元素進行比較，若前者大於後者則進行交換，如此一趟下來最後一趟的就是最大元素，重復以上的步驟，除了已經確定的元素 。

演算法原理：每次對相鄰的兩個元素進行比較，若前者大於後者則進行交換，如此一趟下來最後一趟的就是最大元素，重復以上的步驟，除了已經確定的元素

演算法步驟

1)  設置兩個變數i、j，排序開始的時候：i=0，j=n-1；

2）第一個數組值作為比較值，首先保存到temp中，即temp=A[0]；

3）然後j-- ,向前搜索,找到小於temp後,因為s[i]的值保存在temp中,所以直接賦值,s[i]=s[j]

4）然後i++,向後搜索,找到大於temp後,因為s[j]的值保存在第2步的s[i]中,所以直接賦值,s[j]=s[i],然後j--,避免死循環

5）重復第3、4步，直到i=j,最後將temp值返回s[i]中

6)  然後採用「二分」的思想,以i為分界線,拆分成兩個數組 s[0,i-1]、s[i+1,n-1]又開始排序

排序圖解

演算法原理：從第一個元素開始，左邊視為已排序數組，右邊視為待排序數組，從左往右依次取元素，插入左側已排序數組，對插入新元素的左側數組重新生成有序數組 。需要注意的是，在往有序數組插入一個新元素的過程中，我們可以採用按 順序循環 比較，也可以通過 折半查找法 來找到新元素的位置，兩種方式的效率 取決於數組的數據量

演算法原理：希爾排序也是利用插入排序的思想來排序。希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後演算法再取越來越小的步長進行排序，演算法的最後一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了，插入效率比較高。

排序圖解

選擇排序(Selection sort)是一種簡單直觀的排序演算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬於非常好的一種。

歸並排序，顧名思義就是一種 「遞歸合並」 的排序方法（這個理解很重要）。對於一個數列，我們把它進行二分處理，依次遞歸下去，然後將小范圍的數進行排序，最後將其合並在一起。就實現了歸並排序。

這實際上是運用了 分治思想 ，顯然，想要把一個數列排好序，最終達到的目的就是它的任何一部分都是有序的。這樣的話，我們可以考慮分別把數列分成N多個部分，讓每個部分分別有序，然後再將其統一，變成所有的東西都有序。這樣就實現了排序。這個想法就叫分治思想。

排序圖解

排序圖解

『捌』 編譯原理正規式轉DFA代碼（C#），用窗體的形式顯示。謝謝

NFA/DFA演算法涉及到詞法分析，有窮狀態自動機演算法，屬於計算機領域難度較高的編譯原理部分，你還真敢問呀

『玖』 正則表達式原理

首先先講解下正則表達式的基礎知識：

1.字元串的組成

對於字元串」123「而言，包括三個字元四個位置。如下圖所示：

2.佔有字元和零寬度

正則表達式匹配過程中，如果子表達式匹配到東西，而並非是一個位置，並最終保存到匹配的結果當中。這樣的就稱為佔有字元，而只匹配一個位置，或者是匹配的內容並不保存到匹配結果中，這種就稱作零寬度，後續會講到的零寬度斷言等。佔有字元是互斥的，零寬度是非互斥的。也就是一個字元，同一時間只能由一個子表達式匹配，而一個位置，卻可以同時由多個零寬度的子表達式匹配。

3.控制權和傳動

正則表達式由左到右依次進行匹配，通常情況下是由一個表達式取得控制權，從字元串的的某個位置進行匹配，一個子表達式開始嘗試匹配的位置，是從前一子表達匹配成功的結束位置開始的（例如：（表達式一）（表達式二）意思就是表達式一匹配完成後才能匹配表達式二，而匹配表達式二的位置是從表達式一的位置匹配結束後的位置開始）。如果表達式一是零寬度，那表達式一匹配完成後，表達式二匹配的位置還是原來表達式以匹配的位置。也就是說它匹配開始和結束的位置是同一個。

舉一個簡單的例子進行說明：正則表達式：123

源數據：123

講解：首先正則表達式是從最左側開始進行匹配，也就是位置0處進行匹配，首先得到控制權的是正則表達式中的「1」，而不是源數據中的「1」，匹配源數據中的「1」，匹配成功，將源數據的「1」進行保存到匹配的結果當中，這就表明它佔有了一個字元，接下來就將控制權傳給正則表達式中的「2」，匹配的位置變成了位置1，匹配源數據中的「2」，匹配成功，將控制權又傳動給了正則表達式的「3」，這時候匹配的位置變成了位置2，這時候就會將源數據中的「3」進行匹配。又有正則表達式「3」進行傳動控制權，發現已經到了正則表達式的末尾，正則表達式結束。