編譯原理（三）

（一）有窮自動機

有窮自動機 ( Finite Automata，FA )由兩位神經物理學家

MeCuloch和Pitts於1948年首先提出，是對一類處理系統

建立的數學模型

輸入帶(input tape)：用來存放輸入符號串

讀頭(head )：從左向右逐個讀取輸入符號，不能修改（只讀）、不能往返移動

有窮控制器( finite control )：具有有窮個狀態數，根據當前的狀態和當前輸入符號控制轉入下一狀態

（二）轉換圖 (Transition Graph)

結點：FA的狀態

初始狀態（開始狀態）：只有一個，由start箭頭指向

終止狀態（接收狀態）：可以有多個，用雙圈表示

帶標記的有向邊：如果對於輸入a，存在一個從狀態p到狀態q的轉換，就在p、q之間畫一條有向邊，並標記上a

如果一個串可以被FA識別，則稱該串被FA接收

由一個有窮自動機M接收的所有串構成的集合稱為是該FA定義（或接收）的語言，記為L(M )

（三）有窮自動機的分類

1. 確定的FA (Deterministic finite automata, DFA)

M = ( S，Σ ，δ，S0，F )

S：有窮狀態集

Σ：輸入字母表，即輸入符號集合。假設ε不是 Σ中的元素

δ：將S×Σ映射到S的轉換函數。 s∈S, a∈Σ, δ(s,a)表示從狀態s出發，沿著標記為a的邊所能到達的狀態。

s0：開始狀態 (或初始狀態)，s0∈ S

F：接收狀態（或終止狀態）集合，F? S

S包含｛0，1，2，3｝，Σ 包含｛a,b｝

2.非確定的FA (Nondeterministic finite automata, NFA)

非確定FA和DFA的唯一區別就是從狀態S出發沿著標記為a的邊所能到達的狀態集合（狀態可能有多個）

3.DFA和NFA的等價性

對任何非確定的有窮自動機N ，存在定義同一語言的確定的有窮自動機D

對任何確定的有窮自動機D ，存在定義同一語言的非確定的有窮自動機N

r = (a|b)*abb

正則文法<=> 正則表達式<=>FA

4.帶有「ε-邊」的NFA

r = 0*1*2*

ε-邊表示從狀態A轉移到狀態B不要任何條件

5.帶有和不帶有「ε-邊」的NFA 的等價性

（四）從正則表達式到有窮自動機

由於直接構造DFA比較困難，所以先構造NFA，再從NFA構造DNA

1.根據RE 構造NFA

（五）從NFA到DFA的轉換

例一

由狀態表可知

第一步：狀態A遇見a進入狀態｛A，B｝

第二步：狀態｛A,B｝遇見a仍進入狀態｛A,B｝，狀態｛A,B｝遇見b進入狀態｛B,C｝

第三步：狀態｛B,C｝遇見b仍進入狀態｛B,C｝，狀態｛B,C｝遇見c進入狀態｛C,D｝

第四步：狀態｛C,D｝遇見c仍進入狀態｛C,D｝，否則狀態｛C,D｝直接終止。

例二

首先狀態A遇見0可以進入狀態A，然後由於狀態A的一條為ε-邊，所以狀態A不需要任何條件就可以進入狀態B，同理狀態A也可以進入狀態C

第一步：NFA中A為初始狀態，然而，由於A可以不用任何條件進入狀態B、狀態C，所以初始狀態為｛A，B，C｝。由於初始狀態C在NFA中為一個終止狀態，因此，初始狀態也被標記為終止狀態。此時初始狀態｛A，B，C｝遇見0仍進入狀態｛A，B，C｝，遇見1進入狀態｛B，C｝，遇見2進入狀態C。

第二步：狀態｛B，C｝遇見1仍進入狀態｛B，C｝，遇見2進入狀態C

第三步：狀態C遇見2仍進入狀態C

推薦閱讀：