第三章詞法分析1第1頁，課件共84頁，創作于2023年2月§3.1對于詞法分析器的要求●詞法分析器的功能輸入源程序，輸出單詞符號。單詞符號是一個程序語言的基本語法符號。

●程序語言的單詞符號分類關鍵字(forwhile)

標識符(x1xname)

運算符(+*)

界符({};)

常數(23“abcdf”)功能和輸出形式2第2頁，課件共84頁，創作于2023年2月單詞符號

一個程序語言的關鍵字、運算符和界符都是確定的。但對于標識符和常數的使用是靈活的。詞法分析器所輸出的單詞符號形式：

（單詞種別，屬性值）單詞種別通常用整數編碼。屬性值是反映單詞符號特性或特征的值。本書假定關鍵字、運算符和界符都是一符一種；標識符為一種；常數按類型分種。3第3頁，課件共84頁，創作于2023年2月例如：C的代碼段while(x>=y)x--;<while,->

<(,->

<id,指向x的指針><>=,->

<id,指向y的指針><),-><id,指向x的指針>

<--,-><;,->

經詞法分析器處理后，輸出如下序列：4第4頁，課件共84頁，創作于2023年2月詞法分析器作為一個獨立子程序●好處使整個編譯程序的結構更簡單、清晰和條理化。因為詞法分析比語法分析要簡單得多，可用更有效的特殊方法和工具進行處理。●討論

是否可以把詞法分析器作為獨立一遍呢？

5第5頁，課件共84頁，創作于2023年2月§3.2詞法分析器的設計常常按詞法分析的任務和作為一個獨立子程序來考慮它的設計。3.2.1

輸入、預處理詞法分析器的第一步工作是輸入源程序文本到一個輸入緩沖區中。這樣，詞法分析的工作可以直接在這個緩沖區中進行。在許多情況下，常常把輸入串預處理一下，目的是為了方便單詞符號的識別。

預處理的工作是將源程序中多余的空白符、跳格符、回車符、換行符等編輯性字符以及注釋部分剔除掉，并將結果存入掃描緩沖區中。6第6頁，課件共84頁，創作于2023年2月詞法分析器

預處理子程序詞法分析器單詞符號輸入緩沖區掃描緩沖區源程序7第7頁，課件共84頁，創作于2023年2月掃描緩沖區詞法分析器對掃描緩沖區進行掃描時，一般用兩個指示器(P1,P2)：一個指向當前正在識別的單詞的開始位置，另一個用于向前搜索以尋找單詞的終點。

P1P2120個字符120個字符|標識符|〈=120個字符

|常數|〈=

120個字符…while(x>100)…8第8頁，課件共84頁，創作于2023年2月單詞符號的識別---超前搜索關鍵字的識別（Fortran）例如：(1)do99k=1,10

do99k=1,10(2)do99k=1.10

do99k是變量標識符的識別常數的識別例如：(1)5.E-85-8(2)5.EQ.M5=M算符和界符的識別例如：++,+=,>=9第9頁，課件共84頁，創作于2023年2月

狀態轉換圖狀態轉換圖是設計詞法分析程序的一個好途徑。轉換圖是一張有限的有向圖。結點代表狀態，用圓圈表示，狀態之間用箭弧連接。箭弧上的標記代表在射出結點狀態下可能出現的輸入字符或字符類。一張轉換圖只能含有有限個狀態，其中一個被認為是初態，可以有一個或多個終態（雙圈）。10第10頁，課件共84頁，創作于2023年2月例如①

②

字母字母數字①

②

數字數字其它其它（a）識別標識符的狀態圖（b）識別整數的狀態圖**一個狀態轉換圖可用于識別（或接受）一定的字符串。3311第11頁，課件共84頁，創作于2023年2月

大多數程序語言的單詞符號都可以用轉換圖予以識別。

作為一個綜合例子，我們來構造一個識別某個簡單語言的所有單詞符號的轉換圖。

P42表3.1中列出了這個小語言所有單詞以及它們的種別和內部值。

單詞符號的識別12第12頁，課件共84頁，創作于2023年2月單詞符號種別編碼內碼值beginendifthenelsewhiledo標識符整常數12345671011--------內部字符串二進制形式單詞符號種別編碼內碼值+-*/<=<><::=;13141516171819212223------------小語言單詞符號及內部表示13第13頁，課件共84頁，創作于2023年2月詞法分析的狀態轉換圖*非字母或數字

字母

數字

非數字空白數字*非**其它103*字母或數字

…④13

見P43

…7②⑨⑧*14第14頁，課件共84頁，創作于2023年2月3.2.4狀態轉換圖的實現狀態轉換圖很容易用程序實現。最簡單的辦法是讓每個狀態結點對應一小段程序。假設已有一組全局變量和過程，將它們作為實現轉換圖的基本部分。這些變量和過程見P44。詞法分析器算法見P45。15第15頁，課件共84頁，創作于2023年2月

ch=GetChar();GetBC();if(IsLetter(ch))/*進入關鍵字或標識符識別狀態*/{while(IsLetter(ch)||IsDigit(ch)){Concat();ch=Getchar();}Retract();/*回退一個字符位置*/code=Reserve();/*查找保留字表*/if(!code)return(code,’-’);else{value=InsertId(strToken);return($ID,value);}}else/*進入其它單詞符號的判斷狀態*/16第16頁，課件共84頁，創作于2023年2月狀態轉換圖的實現狀態轉換圖容易用程序實現。最簡單的辦法是讓每個狀態結點對應一小段程序。下面引進一組全局變量和過程，將它們作為實現轉換圖的基本部分。這些變量和過程是：(1)ch字符變量，存放最新讀進的源程序字符。(2)strToken字符數組，存放構成單詞符號的字符串。(3)GetChar讀字符函數，從輸入緩沖區中讀進源程序的下一個字符到ch，并把讀字符指針指向下一個字符。(4)GetBC 函數，檢查ch中的字符是否為空白字符，若是空白字符，則反復調用GetChar()，直到ch中讀入一個非空白字符為止。17第17頁，課件共84頁，創作于2023年2月(5)Concat函數，將ch中的字符與token中的字符串連接。(6)IsLetter

IsDigit布爾函數，分別判斷ch中的字符是否為字符或數字。(7)Reserve整數函數，對token中的字符串查找關鍵字表，若它是一個關鍵字則返回它的編碼，否則返回標識符的種別碼10。(8)Retract函數，讀字符指針回調一個字符位置。(9)Return函數，收集并攜帶必要的信息返回調用程序，即返回語法分析程序。(10)dtb十進制轉換函數，將token中的數字串轉換成二進制數值表示，并以此作為函數值返回。18第18頁，課件共84頁，創作于2023年2月思考題：1.令∑={a,b},畫出接受∑上含有偶數個a的字符串的狀態轉換圖。2.畫出狀態轉換圖，它接受∑={0,1}上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。①②aabb120010012119第19頁，課件共84頁，創作于2023年2月§3.3正規表達式與有限自動機詞法分析器的自動生成可依據正規表達式和有限自動機的理論。實際上，狀態轉換圖與正規表達式和有限自動機在描述語言能力方面是等價的。3.3.1正規式與正規集

對于字母表∑，我們感興趣的是它的一些特殊字集，即正規集。我們將使用正規式這個概念來表示正規集。下面是正規式和正規集的遞歸定義：

1）ε和Φ都是∑上的正規式，它們所表示的正規集分別為{ε}和Φ；

2）任何a∈∑,a是∑上的一個正規式，它所表示的正規集為{a}；

20第20頁，課件共84頁，創作于2023年2月正規式和正規集的遞歸定義（續）

3）假定U和V都是∑上的正規式，它們所表示的正規集分別記為L(U)和L(V)，那么，(U|V)、(U·V)和(U)*也都是正規式。它們所表示的正規集分別為L(U)∪L(V)、L(U)·L(V)（連接積）和(L(U))*（閉包）。僅由有限次使用上述三步驟而得到的表達式才是∑上的正規式。僅由這些正規式所表示的字集才是∑上的正規集。

算符的優先順序：先“*”，次“·”，后“|”。21第21頁，課件共84頁，創作于2023年2月例3.1

令∑={a,b}，下面是∑上的

正規式和相應的正規集。正規式

正規集

ba* ∑上所有以b為首，后跟任意多個a的字。

a(a|b)* ∑上所有以a為首的字。(a|b)*(aa|bb)(a|b)* ∑上所有含有兩個相繼的a

或兩個相繼的b的字。22第22頁，課件共84頁，創作于2023年2月例3.2

令∑={a，b，0，1}，則：

正規式

正規集

(a|b)(a|b|0|1)*∑上的“標識符”的全體

(0|1)(0|1)*∑上的“數”的全體23第23頁，課件共84頁，創作于2023年2月正規式的等價性若兩個正規式所表示的正規集相同，則稱兩者等價。例如

b(ab)*=(ba)*b(a|b)*=(a*|b*)*

令U、V和W均為正規式，則下列關系成立：

U|V=V|U 交換律

U(V|W)=(U|V)|W 結合律

U(VW)=(UV)W 結合律

U(V|W)=UV|UW分配律

(V|W)U=VU|WU5)εU=Uε=U 注意:UV≠VU24第24頁，課件共84頁，創作于2023年2月思考題：寫出下面正規式1.令∑={a,b},含有偶數個a的∑上的字符串。

2.

每個1都有0直接跟在右邊的二進制串。(b*|ab*a)*(0|10)*①②aabb1200125第25頁，課件共84頁，創作于2023年2月確定的有限自動機一個確定有限自動機(DFA)M是一個五元式：

M=(S,∑,δ,s0

,F)其中：S是一個有限集，它的每個元素稱為一個狀態。∑是一個有窮字母表，它的每個元素稱為一個輸入字符。δ是一個從S×∑至S的單值部分映射。δ(s,a)=s’意味著：當現行狀態為s、輸入字符為a時，將轉換到下一狀態s’。我們稱s’為s的一個后繼。

s0∈S，是唯一的初態。

F

S是一個終態集（可空）。26第26頁，課件共84頁，創作于2023年2月狀態轉換矩陣一個DFA可用一個矩陣表示，該矩陣的行表示狀態，列表示輸入字符，矩陣元素表示δ(s,a)的值。這個矩陣稱為狀態轉換矩陣。例3.2

有DFAM=(S,∑,δ,s0

,F)其中：

S={0,1,2,3},∑={a,b},s0

=0,F={3},

δ(0,a)=1 δ(0,b)=2

δ(1,a)=3 δ(1,b)=2

δ(2,a)=1 δ(2,b)=3

δ(3,a)=3 δ(3,b)=327第27頁，課件共84頁，創作于2023年2月狀態轉換矩陣狀態轉換圖字符狀態ab

0

1

2

1

3

2

2

1

3

3

3

30

③aaabbba,b②

①28第28頁，課件共84頁，創作于2023年2月DFAM

接受的語言對于∑*中的任何字α，若存在一條從初態到某一終態結點的通路，且這條通路上的所有弧的標記符連接成的字等于α，則稱α可為DFAM所識別(或接受)。

DFAM所能識別的字的全體，稱為DFAM所接受的語言，記為L(M)。注意：若M的初態結點又是終態結點，則空字ε可被M所識別。29第29頁，課件共84頁，創作于2023年2月例如：有DFAM

如下：0

③aaabbba,b②

①M可接收的字：aabbaaaaabbabbabaabaaaabbb…M接收的語言為：含有兩個相繼a或b的a,b字符串。30第30頁，課件共84頁，創作于2023年2月非確定的有限自動機一個非確定有限自動機(NFA)M是一個五元式：

M=(S,∑,δ,S0

,F)其中：S是一個有限集，它的每個元素稱為一個狀態。∑是一個有窮字母表，它的每個元素稱為一個輸入字符。δ是一個從S×∑*至S的冪集的映射,即:

δ:S×∑*2S4)S0

S，是一個非空初態集。5)F

S是一個終態集（可空）。31第31頁，課件共84頁，創作于2023年2月同樣,一個NFAM

也可表示成狀態轉換圖。NFA狀態轉換圖與DFA狀態轉換圖的主要區別：（1）箭弧上的標記可以不同。DFA的標記是∈∑上的單個字符，而NFA的標記是∈∑*上的字（可以是ε字）；（2）映射函數δ的定義不同，DFA的δ是單值函數，而NFA的δ是多值函數。0DFA00NFA32第32頁，課件共84頁，創作于2023年2月對于∑*中的任何字α，若存在一條從某個初態到某一終態結點的通路，且這條通路上所有弧的標記字依序連接成的字（忽略ε字）等于α，則稱α可為NFAM所識別(或接受)。

NFAM所能識別的字的全體，稱為NFAM所接受的語言，記為L(M)。NFAM接受的語言33第33頁，課件共84頁，創作于2023年2月例如：下圖就是一個NFAM它所能識別的是含有兩個相繼a或兩個相繼b的字符串。

x⑤①②⑥y

aaaabbbbεεεε34第34頁，課件共84頁，創作于2023年2月NFA與DFA等價顯然，DFA是NFA的特例。但是可以證明對于每個NFAM，都存在一個DFAM”，使

L(M)=L(M”)證明：（構造性證明）

（1）假定NFAM=<S,∑,δ,S0,F>，對M的狀態轉換圖進行以下改造：

①引進新的初態結點X和終態結點Y，并且X、Y∈S，從X到S0的任意狀態結點連一條ε箭弧，從F中任意狀態結點連一條箭弧ε到Y。

35第35頁，課件共84頁，創作于2023年2月②對M的狀態轉換圖進行如下替換：

①② 代之以 ① k ②

① ② 代之以 ① ②

① ② 代之以 ① k ②

重復這種分裂過程直至狀態轉換圖中的每條箭弧上的標記或為ε，或為∑中的單個字母。將最終得到的NFA記為M’。顯然,L(M)=L(M’)ABA|BABBAA*εεA36第36頁，課件共84頁，創作于2023年2月（2）將NFAM’進一步變換成等價的DFAM”方法如下：

①

假定I是M’的狀態集的子集，定義I的ε閉包ε_CLOSURE(I)為：若q∈I，則q∈ε_CLOSURE(I)；若q∈I，那么從q出發經過任意條ε弧而能達到的任何狀態q’都∈ε_CLOSURE(I)②假定I是M’的狀態子集，a∈∑，定義

Ia=ε_CLOSURE(J)其中，J是那些可以從I中的某一狀態結點出發經過一條a弧而到達的狀態結點的全體。37第37頁，課件共84頁，創作于2023年2月③假定∑={a1,…,ak}。構造一張含有k+1列的表

置該表的首行首列為ε_CLOSURE(X)。若某行第一列狀態子集I已確定，求出其它列Iai

(i=1,2,…,k)，然后檢查該行上的所有狀態子集，將其未出現在第一列的狀態子集填入后面空行的第一列。重復上述過程，直至所有狀態子集均在該表的第一列出現過。因為M’的狀態子集的個數是有限的，所以上述過程必定在有限步內終止。

38第38頁，課件共84頁，創作于2023年2月（3）將所構造出的表視為狀態轉換矩陣將其中每個狀態子集視為一個新的狀態。顯然，該表唯一刻劃了一個DFAM”。它的初態就是該表中的首行首列的那個狀態子集，終態是那些含有原終態Y的狀態子集對應的新狀態。顯然,L(M)=L(M’)=L(M”)。

上述把NFA確定化為DFA的方法稱為子集法。 39第39頁，課件共84頁，創作于2023年2月例如：正規式(a|b)*(aa|bb)(a|b)*求對應的NFAM，并轉換出等價的DFAM’。NFA(2)NFA(1)解答：a|ba|bεε⑤①②⑥aa|bbaaaabbbbεεεε③

x⑤①②⑥y

④40第40頁，課件共84頁，創作于2023年2月利用子集法求狀態轉換表：aaaabbbbεεεε③

x⑤①②⑥y④IIaIb{x,5,1}{5,3,1}{5,4,1}{5,3,1}{5,2,3,1,6,y}{5,4,1}{5,4,1}{5,3,1}{5,2,4,1,6,y}…41第41頁，課件共84頁，創作于2023年2月繼續求新的子集：I、Ia、Ib，得出下表：

I

Ia

Ib0{X,5,1}{5,3,1}{5,4,1}1{5,3,1}{5,3,1,2,6,Y}{5,4,1}2{5,4,1}{5,3,1}{5,4,1,2,6,Y}3{5,3,1,2,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}4{5,4,1,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}5{5,4,1,2,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}6{5,3,1,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}01213221533446556563442第42頁，課件共84頁，創作于2023年2月對所有的狀態子集重新命名，由此而得：

①③④

②⑤⑥

0aaaaaaabbbbbb等價的DFA（未化簡）如下：43第43頁，課件共84頁，創作于2023年2月例題1（1）畫NFA（2）加X，Y構造一個DFA，它接受{a,b}上含有偶數個a的字符串。①②③bbaaεbbbaaεb

x

①②③yεε44第44頁，課件共84頁，創作于2023年2月(3)用子集法求狀態轉換矩陣

I

Ia

Ib

0

{X,1}

{2}

{1}

1

{1}

{2}

{1}

2

{2}

{3,1,y}

{2}

3

{3,1,Y}

{2}

{3,1,Y}bbaaεb

x

①②③yεε45第45頁，課件共84頁，創作于2023年2月

(4)重新命名得DFA

I

Ia

Ib

0

{X,1}

{2}

{1}

1

{1}

{2}

{1}

2

{2}

{3,1,y}

{2}

3

{3,1,Y}

{2}

{3,1,Y}021121232323bbaab

0①②③

aba46第46頁，課件共84頁，創作于2023年2月例題2（1）DFA

（2）正規文法G(S):構造一個DFA，它接受{a,b}上含有偶數個a的字符串。然后寫出其等價的正規文法。①②③bbaaba

S→aA|bSA→aB|bA|aB→aA|bB|b47第47頁，課件共84頁，創作于2023年2月正規文法與有限自動機的等價性對于正規文法G

和有限自動機M，如果：

L(G)=L(M)則稱

G

和

M

是等價的。結論：

（1）對每一個右（或左）線性文法G，都存在一個有限自動機(FA)M，使得：

L(M)=L(G)

（2）對于每一個FAM，都存在一個右線性文法GR和左線性文法GL，使得：

L(M)=L(GR)=L(GL)48第48頁，課件共84頁，創作于2023年2月證明(1)對每一個右線性文法G，都存在一個FAM，使得:L(M)=L(G)證明：(構造性證明)

設右線性文法G=<VT,VN,S,P>，將VN的每個非終結符視為狀態符號，并增加一個終態狀態符f∈VN

。令：FAM=<

VN∪{f},VT,δ，S，{f}>其中δ定義如下：●對A∈VN及a∈VT∪{ε}，若有

Aa，則令δ(A,a)=f●對A∈VN及a∈VT∪{ε}，若有

AaA1|aA2|…|aAk，

則令δ(A,a)={A1，A2，…，Ak}顯然，上述構造的M是一個NFA。可以證明：

∈L(G)當且僅當

∈L(G)49第49頁，課件共84頁，創作于2023年2月顯然Aa

Af

AaB

ABaa令

=a1a2…

ak其中ai∈VT若

∈L(G)即S

則Sa1B1a1a2B2

…a1a2…ak-1Bk-1a1a2…ak因此，存在一條從初態S到終態f

的通路，其箭弧上的標記依次連接起來恰好為a1a2…

ak

，故

∈L(M)

*a1a2ak-1akSB1B2Bk-1f50第50頁，課件共84頁，創作于2023年2月例題3已知正規文法G

如下，構造其等價的FAM

。

G:SaA|bSAbA|a|aBBaA|bB|b

NFA解：

SAB

fabbaabab51第51頁，課件共84頁，創作于2023年2月證明(2)對于每一個DFAM，都存在一個右線性文法G，使得：L(M)=L(G)證明：設DFAM=<S，

∑，δ，s0，F>(1)若s0∈F，令G=<∑，S，s0，P>其中P定義如下：

對任意a∈∑及A，B∈S，若有

δ(A,a)=B，則①若B∈F時，令AaB②若B∈F時，令Aa|aB可以推出：

∈L(M)當且僅當

∈L(G)(2)若S0∈F，即δ(S0

，ε)=S0

，但是，ε∈L(G)。此時增加一個S0’∈S，且令S0’

ε|S0，并為開始符號。顯然，對G修改后的G’，有L(G’)=L(M)考慮出弧！52第52頁，課件共84頁，創作于2023年2月例題4設DFAM如下，構造等價的正規文法。bbaaba

①②③

SaA|bSAa|aB|bABaA|b|bBaba

①②b

S’

S|

εSaA|bS|bAa|aS|bA53第53頁，課件共84頁，創作于2023年2月例題5bbaa

①②③解：

SaA|bSAbA|a|aB

注意:

若終態無出弧，則去掉該非終結符54第54頁，課件共84頁，創作于2023年2月證明(1)對每一個左線性文法G，都存在一個FAM，使得：

L(M)=L(G)證明：設左線性文法G=<VT,VN,S,P>，將VN的每個非終結符視為狀態符號，并增加一個初態符q0∈

VN

。令：FAM=<

VN∪{q0},VT,δ，q0

，{S}>其中δ定義如下：●對A∈VN及a∈VT∪{ε}，若有：

Aa，則令δ(q0,a)=A●對A∈VN及a∈VT∪{ε}，若有：

A1Aa，A2Aa，…，AkAa，

則令δ(A,a)={A1，A2，…，Ak}顯然，上述構造的M是一個NFA。可以證明：

W∈L(G)當且僅當W∈L(M)55第55頁，課件共84頁，創作于2023年2月顯然Aa

q0A

ABa

BAaa令

=a1a2…

ak其中ai∈VT若

∈L(G)即S

則SBk-1ak

Bk-2ak-1

ak

…B1a2…aka1a2…ak因此，存在一條從初態q0

到終態S的通路，其箭弧上的標記依次連接起來恰好為a1a2…

ak

，故

∈L(M)

*akak-1a2a1SBk-1Bk-2B1q056第56頁，課件共84頁，創作于2023年2月證明(2)對于每一個DFAM，都存在一個左線性文法G，使得：L(M)=L(G)證明：設DFAM=<S,∑

，δ，S0，{f}>

令G=<∑，S，f

，P>其中P定義如下：

若

δ(S0,a)=A，則Aa|S0a

若

δ(A,a)=B

，則BAa（其中A≠S0）可以證明：

∈L(M)當且僅當

∈L(G)考慮入弧！57第57頁，課件共84頁，創作于2023年2月例3.4(1)1）已知DFAM→求GR

ABCD0100110,1解：右線性文法GR(A):A→0|0B|1DB→0D|1CC→0|0B|1DD→0D|1D58第58頁，課件共84頁，創作于2023年2月例3.4(2)2）已知GR→求FAM右線性文法GR(A):A→0

|0B|1DB→0D|1CC→0

|0B|1DD→0D|1DABCD0100110,1f0059第59頁，課件共84頁，創作于2023年2月例3.4(3)2）已知FAM→求GL

ABCD0100110,1f00解：左線性文法GL(f):f→0|A0|C0D→1|A1|B0|C1|D0|D1C→B1B→0|A0|C0A無入弧！60第60頁，課件共84頁，創作于2023年2月正規式與有限自動機的等價性可以證明：

（1）對任何FAM，都存在一個正規式r,使得：

L(r)=L(M)

（2）對任何正規式r

，都存在一個FAM，使得

L(M)=L(r)結論：

正規文法、正規式、NFA、DFA在接受語言能力上是等價的。61第61頁，課件共84頁，創作于2023年2月證明

對任何FAM，都存在一個正規式r,使得：

L(r)=L(M)證明：

(1)引進新的初態結點X和終態結點Y，并且X、Y∈S，從X到S0的任意狀態結點連一條ε箭弧，從F中任意狀態結點連一條箭弧ε到Y。62第62頁，課件共84頁，創作于2023年2月（2）逐步消除中間狀態結點，使之只剩下X，Y為止。在消除結點的過程中，逐步用正規式來標記箭弧，方法如下：①②③代之為①②V1V2V1V2①②代之為①②V1|

V2V1V2①②③代之為①②V1V2V1V2*

V3V3r最后得到:xy63第63頁，課件共84頁，創作于2023年2月證明:

對任何正規式r

，都存在一個FAM，使得

L(M)=L(r)證明：（采用歸納證明法）（1）若r具有0個運算符，則r=

或r=或r=a此時，對應的FA分別為：q0q0q0qa64第64頁，課件共84頁，創作于2023年2月（2）假設結論對少于k(k>0)個運算符的r成立。（3）當r具有k個運算符時，有三種情形：

①

r=r1|r2

q0q1fM1f1q2M2f2

65第65頁，課件共84頁，創作于2023年2月②

r=r1.r2q1M1f1q2M2f2

③

r=r1*q

q1M1f1f

66第66頁，課件共84頁，創作于2023年2月例題6

1.寫出{a,b}上不以a開頭，以aa結尾的正規式和DFA。解:正規式：

b(a|b)*aaabab①②③④a

I

Ia

Ib

{1}

{2}

{2}

{2,3}

{2}

{2,3}

{2,3,4}

{2}

{2,3,4}

{2,3,4}

{2}NFA：DFA：bbaa②③④abb67第67頁，課件共84頁，創作于2023年2月例題7

寫出下面NFA對應的正規式（1）

baa②③b解：令

r=ab*(a|b)正規式:R=r(ar)*即：

ab*(a|b)(aab*(a|b))*解：ab*(a|b)a（2）

aa②③bb68第68頁，課件共84頁，創作于2023年2月確定有限自動機的化簡一個確定有限機M的化簡：即尋找一個狀態數比M少的DFAM’，使得：

L(M)=L(M’)

●什么是等價狀態？如果從狀態s

出發能讀出某個字

而停止于終態，從狀態t

出發也能讀出相同的字

而停止于終態；反之亦然，則稱狀態s和t是等價的。●兩個狀態是可區別的？如果DFAM的兩個狀態s

和t

不等價；則稱狀態s

和t

是可區別的。69第69頁，課件共84頁，創作于2023年2月例題8狀態2與3是等價的。狀態2與1是可區別的。DFA：bbba②③④aab70第70頁，課件共84頁，創作于2023年2月●

DFAM的狀態最少化過程將M的狀態集分割成一些不相交的子集，使得任何不同的兩個子集中的狀態都是可區別的，而同一子集中的任何兩個狀態都是等價的。最后，在每個子集中選出一個代表，同時消去其它等價狀態。I1197352846I4I3I271第71頁，課件共84頁，創作于2023年2月將DFA最小化的方法

(1)先把DFAM的終態與非終態分開，分成兩個不同的子集；

(2)對每個子集I中的狀態分別考察它們是否是可區別的，設I={q1,…qk}

若存在一個輸入字符a使得Ia不全在現行劃分的同一子集I’中，就將I分為兩個子集I1，I2

：

I1=

{s|s是經a弧到達同一子集的狀態

}

I2=I-I1

(3)重復（2）過程，直到每個狀態子集中的狀態都是等價的。72第72頁，課件共84頁，創作于2023年2月

設I={q1,…qk

}，選q1

為代表，在原來的DFA中，凡導入到q2,……,qk的弧，都改成導入到q1

，然后刪除q2,……,qk。若I中含有原來的初態，則q1是新初態；若I中含有原來的終態，則q1是新終態。可以證明：如此化簡之后得到的DFAM’和原來的M是等價的，即：L(M)=L(M’)(5)

若從M’中再刪除所有無用狀態(從初態開始不可達的狀態)，則M’就是含有最少狀態的DFA。(4)在每個子集I中選取一個狀態代表其它狀態73第73頁，課件共84頁，創作于2023年2月例題9將DFA最小化

I1={1,2,3}I2={4}bbba②③④aab

I11={1}I12={2,3}I2={4}最小化DFA②④baabb74第74頁，課件共84頁，創作于2023年2月例題3.6設DFAM如下，將其最少化。0aaaaaaabbbbbb

①③④

②⑤⑥

(1)

I1={0,1,2}