第三章 词法分析

第三章词法分析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}