2015年4月27日 星期一

Formal Language - Ch2 非決定性有限自動機 Nondeterminism Finite automata, NFA

 


非決定性有限自動機(Nondeterminism Finite automata, NFA)定義
一個非決定性有限自動機是含有5個元素的 5-tuple$(Q,Σ,δ,q_0,F)$ ,意義分別是 (狀態集$Q$, 字母集$Σ$, 轉移函式$δ$, 開始狀態$q_0$, 結束狀態$F$) ,從定義中可知F可以是空集合,表示沒有可以接受的狀態。


原文定義如下:
A finite automaton is a 5-tuple $(Q,Σ,δ,q_0,F)$ , where
  1. $Q$ : is a finite set called the states
  2. $Σ$ : is a finite set called the alphabet
  3. $δ$ : $Q \times Σ_\varepsilon \rightarrow P(Q)$, is the transition function //箭頭線段代表狀態的變化
  4. $q_0 ∈ Q$ : is the start state //開始狀態
  5. $F ⊆ Q$ : is the set of accept states or final states //接受狀態

看一個狀態圖例子最容易理解:




[用心去感覺] DFA和NFA的不同之處
重點是定義3.的轉移函式
  • 可不消耗($Σ_\varepsilon$)字串換狀態, 所以可能有剪頭可以自動轉移不用吃字元。
  • 型別變成集合(冪集,power set),因為DFA同時走很多條路
  • 注意在追蹤狀態時,是同時走多條路,其中一條路接受就接受,有點平行計算的感覺,不是選擇也不是機率。
  • NFA下的「計算」定義類似,注意事項亦相同。




DFA和NFA等價 (Equivalence of DFAs and NFAs)
Theorem : Every NFA has an equivalent DFA
我們要證明NFA和DFA等價,也就是任找一個NFA我們都可以找到一個DFA使兩者recognize的language相同,反之亦然。

DFA to NFA : 顯然成立,把轉移函式改一下型別即可。
DFA to NFA : 改寫方式如下
  1. 狀態集 : $Q' = P(Q)$,取power set。
  2. 轉移函式 : $\delta(R,a) = \bigcup_{r \in R}  \delta(r,a)$
  3. 起始狀態 : $q_0' = \{q_0\}$
  4. 結束狀態 : $F' = \{R \in Q'\ |\ R\ contain\ an\ accept\ state\ of\ N\ \} $
*$\varepsilon$處理 : 把可以走到的加進去set中,例如有a-d路徑,則{a,b}變成{a,b,d}

下面有一個實際的例子 : 





Regular Operations正確性證明
因為證明出DFA = NFA,因此可以使用NFA來證明DFA各種operation是可行的。






Reference

交大陳穎平教授正規語言講義





技術提供:Blogger.