2hhh第及4章 词法分析

第2章 词法分析词法分析的任务:从左至右逐个字符地对源程序进行扫描,产生一个一个的单词符号,从而把字符串形式的源程序变换成单词串形式的中间程序。词法分析程序也叫词法分析器或扫描器。字符串形式字符的源程序词法分析器符号表单词单词串形式的源程序词法分析可采用如下两种处理结构:(1)把词法分析程序作为主程序。

词法分析作为独立的一遍来完成。(2)把词法分析程序作为语法分析程序调用的子程序。进行语法分析时,每当需要一个单词时便调用词法分析程序。字符串形式字符的源程序单词词法取下一单词语法分符分析号析器表器词法分析器设计方法一个简单的词法分析器示例正规表达式与FA简介正规表达式到FA的构造词法分析器的自动生成2.1

词法分析器的设计方法2.1.1

单词符号的分类与输出形式1.单词符号分类单词符号是程序语言的基本语法单位。程序语言中的单词符号通常可分为如下五种:保留字:如if,else,while,do标识符:用于标记常量、变量、数组、函数、类型等的名字常数:如实型0.628,布尔型True运算符:如+,-,*,/,>,<界符:分界符号,如,;()注意:一个程序语言的保留字、运算符和界符的个数是确定的,而标识符和常数的个数不确定。2.单词符号的输出形式单词符号通常表示为二元式:(单词种别,单词自身的值)(1)单词种别单词种别表示单词的种类。一个语言的单词符号如何分类、分为几类取决于处理上的方便。通常,每种单词对应一个整数码。保留字:可全体视为一种,也可一字一种;标识符:统归为一种;常

数:

统归为一种,

或按整型、实型、布尔型等分为几种;运算符和界符:统归为一种,或一符一种(2)单词自身的值若一个种别只含一个单词,则其种别编码代表自身的值。若一个种别含多个单词,则除种别编码外,还需给出单词自身的值,从而把同一种类的不同单词区分开。说明:标识符自身的值为标识符自身的字符串,而常数自身的值为常数本身的二进制数值;可以用指向某表格中一个特定项目的指针区分同一种类中的不同单词。例如,标识符可用它在符号表中的入口指针作为自身的值;常数可用它在常数表中的入口指针作为自身的值。在词法分析中,可以用状态转换图来识别单词。在状态转换图中,结点代表状态,结点之间用有向边连接,有向边上可标记字符。考虑右图中状态i,若读入x,则转到状态j;若读入y,则转到状态k。jkixy2.1.2

状态转换图说明:状态转换图中的状态数目是有限的,其中必有一个初态和若干个终态。每个

终态对应一类单词,终态用双圈表示,以区别于其它状态。01222字母

其它*识别标识符的状态转换图如下:字母或数字识别无符号整数的状态转换图如下:01222数字数字其它**0·1

26数字数字E

+/-

5数字数字 其它

7数字其它其它E数字 数字3

4识别无符号数的状态转换图如下:在状态转换图中,到达终态意味着识别出一个单词符号,因此,终态时输出相应单词的种类编码。若到达终态时多读入了一个符号,则识别出该单词后再把多读入的那个符号退回。此类情况在终态上以*作为标识。对于一个不含回路的分支状态,可用一个switch()语句或一组if-else语句来实现。考虑如下所示的状态转换图,其对应的switch语句如下:jki字母数字状态i对应的switch语句如下:s

=

getchar

(

);switch

(s)

{case

"a":…case

"z":实现状态j功能的语句;break;case"0":…case

"9":实现状态k功能的语句;}jki字母数字对于一个含回路的状态,可用一个

while语句来实现。考虑下述状态转换图,其对应的while语句如下:ij字母或数字其它状态i对应的while语句:getchar

(

);while

(

letter(

)||digit(

)

)igetchar

();实现状态j

功能的语句;j字母或数字其它状态转换图的终态一般对应一个return()语句,意味着从词法分析器返回到调用段,通常返回到语法分析器。2.2

一个简单的词法分析器示例大多数程序语言的单词符号都可用状态转换图予以识别。下面利用状态转换图构造一个C语言子集的简单词法分析器。2.2.1

C语言子集的单词符号表示假定一个C语言子集的所有单词符号为:while,if,else,switch,case,标识符,常数,+,-,*,<,<=,=,==,;。其种别编码和内码值如下表所示:表2.1 一个C语言子集的单词符号及其种别编码和内码值单词符号种别编码助记符内码值while1reswhileif1resifelse1reselseswitch1resswitchcase1rescase标识符2idid位置说明:直接使用整数编码不利于记忆,该例中采用一些助记符表示种别编码。单词符号种别编码助记符内码值常数3numnum位置+4op+–4op-*4op*<=5ropLE<5ropLT=

=5ropEQ=6=_;7;_2.2.2

C语言子集对应的状态转换图首先,对输入串做预处理,即剔除多余的空格、注释等。其次,把保留字作为一类特殊标识符处理,即当状态转换图识别出一个标识符时,查保留字表以确定它是否为一个保留字。C语言子集对应的状态转换图如下:返回(op,*)返回(rop,LE)返回(rop,EQ)012

*

返回(id,id位置)或返回(res,保留字码)开始空白字母或数字非字母数字3数字字母数字+*811<=其它==其它;其它4*返回(num,num位置)返回(op,+)返回(op,

)非数字567910

*

返回(rop,LT)1213

*

返回(=,_)返回(;,_)报错1415

*说明:状态2识别出一个单词符号后,需先查保留字表。若匹配,则为保留字,否则为标识符。若为标识符,还需查符号表。若符号表中没有该标识符,则先登录到符号表中,再返回它在符号表中入口地址作为内码值;若符号表中有该标识符,则直接返回其入口地址作为内码值。状态4识别出一个常数后,需先把它转换成二进制常数,再登录到常数表,然后返回它在常数表中入口指针作为内码值。2.2.3

状态转换图的实现状态转换图易于用程序实现,最简单的办法是让每个状态对应一小段程序。对于C语言子集对应的状态转换图,首先引进一组变量和过程:character:字符变量,存放一个最新读入的源程序字符。token:字符数组,存放构成单词符号的字符串。getbe():若character中字符为空,则调用getchar(),直至character为非空字符。concatenation():把token中字符串与character中字符连接作为token中的新字符串。letter()和digit():判断character中字符是否为字母/数字,若是返回true,否则返回false。reserve():按token数组中字符串查保留字表,若是保留字则返回

其编码,否则返回0。retract():扫描指针回退一个字符,同时将character置为空。buildlist():将标识符登录到符号表或将常数登录到常数表。error():进行出错处理。C语言子集对应的的词法分析器:token=

"

";/*token数组初始化为空*/s

=

getchar(

);/*剔除空格*/getbe(

);switch

(s){case

"a":……case

"z":while

(letter(

)

||

digit(

))

{concatenation(

);/*把s中字符送token数组*/getchar();}retract(

);/*扫描指针回退1个字符*/c

=

reserve(

);if

(c

=

=

0)

{buildlist();/*把标识符登录到符号表*/return(id,id在符号表中入口指针);}else

return(res,保留字码);break;case

"0":…case

"9":while

(digit(

))

{concatenation(

);getchar(

);}retract(

);buildlist(

);/*把常数登录到常数表*/return(num,num在常数表入口指针);break;case

"+":

return

("+",

_

);

break;case

"

":

return

("

",

_

);

break;case

"*":

return

("*",

_

);

break;case

"<":getchar(

);if

(character

=

=

"=")return

(relop,

LE);else

{

retract(

);return

(relop,

LT);

}break;case

"=":getchar(

);if

(character

==

"=")return

(relop,

EQ);else

{

retract(

);return

("=",

_

);

}break;case

";":

return

(";",

_

);

break;default: error

(

);}2.3

正规表达式与有限自动机简介2.3.1

正规表达式与正规集利用状态转换图能有效地构造词法分析器。为便于词法分析器的自动生成,需把状态

转换图的概念形式化。正规表达式就是状态转换图的一种形式化表示法,它可以表示单词符号的结构,从而精确定义单词符号集。正规表达式简称为正规式,正规式表示的集合称为正规集。以标识符为例:标识符是以字母开头的字母数字串。标识符的正规式为:letter

(

letter

|

digit

)*其中并置表示连接,|表示两者选一,*表示0次或多次引用。标识符的正规集为:标识符的正规式表示的集合。例如,{a,b,ab,a1,ab1,…}正规式和正规集的递归定义:(1)

和分别为{为字母表

上的正规式,

它们表示的正规集}和Ф;(2)a

是(3)若R,S是①R|S是②R

S是上正规式,正规集为{a};上正规式,其正规集为L(R),L(S),则上正规式,其正规集为L(R)∪L(S);上正规式,其正规集为L(R)L(S);{连接积}③

(R)*是

上正规式,

其正规集为(L(R))*;

{闭包}(4)仅有限次使用(1)~(3)得到的式子是

上正规式,其集合是

上正规集。几点说明:1)

上字是由中字符构成的一个有穷序列。不包含任何字符的序列称为空字

。)。*表示

上所有字的全体(包括例如,

若

={a,

b}则

*={,

a,

b,

aa,

ab,

ba,

bb,

aaa,

…}2)

Ф表示不含任何元素的空集{}。注意 、

Ф、{

}的区别：表示不包含任何字符的序列,

它是正规集中一个元素;

Ф表示不含任何字的集合,

是一个正规集;

{

}表示由空字组成的集合。可使用圆括号改变运算次序。规定:*优先于·,·优先于|,在不引起混淆时,可省略括号。正规式R和S的连接可形式化为RS={

|

∈R

&

∈S}例如,R={a,b},S={1,2},RS={a1,a2,b1,b2}5)R自身的n次连接记为:Rn=RR…RR0

={

},R*

=R0∪R1∪R2∪R3∪…{闭包}R+=RR*

{R的正闭包}R*中的字是由R中字有限次连接而成。6)对于正规式R和S,若正规集L(R)=L(S),则称R和S等价,记为R=S。正规式具有下列性质:交换律:R|S=S|R结合律:R|(S|T)=(R|S)|TR(ST)

=

(RS)T分配律:R(S|T)=RS|RT(R|S)T

=

RT|ST同一律: R

=

R =

R例2.1Σ={a,b},R=a(a|b)*是Σ上正规式,试求R表示的正规集。解:L(R)=L(a(a|b)*)=L(a)L((a|b)*)=

L(a)

(L(a|b))*=

L(a)(L(a)∪L(b))*=

{a}({a}∪{b})*=

{a}{a,b}*=

{a}{ ,

a,

b,

aa,

ab,

ba,

bb,

aaa,

…}=

{a,

aa,

ab,

aaa,

aab,

aba,

abb,

aaaa,…例2.2 判断下述正规式是否等价:(1)(a|b)*与a*|b*(2)(ab)*与a*b*(3)(a|b)*与(a*b*)*解:(1)(a|b)*与a*|b*(a|b)*对应的正规集其a,b可任意交替出现,如abbaaab…,而a*|b*对应的正规集只可出现任意个a或任意个b,因此两者不等价。(2)(ab)*与a*b*(ab)*对应的正规集以任意个ab对出现,即ababab…,而a*b*对应的正规集是

任意个a后接任意个b,即a…ab…b,因此两者不等价。(3)(a|b)*与(a*b*)*(a|b)*对应的正规集中a,b可任意交替

出现,

如aababbb,

而(a*b*)*可采用如下的方法得到相应的字:

(a*b*)*(a*b*)(a*b*)

(a2b1)(a1b3)

aababbb。反之,

(a*b*)*产生的任意字也可由(a|b)*得到,

因此两者等价。例2.3

证明:

若L(a+)={a}*-{

},则a+=aa*证明:

L(a+)

={a}*-{

}={ ,

a,

a2,

a3,

…}-{

}={a,

a2,

a3,

…}={a}{ ,

a,

a2…}={a}{a}*=L(a)L(a*)=L(aa*)故a+=aa*2.3.2

有限自动机有限自动机(Finite

Automaton,FA)是一般化的状态转换图,它分为确定有限自动机和非确定有限自动机。确定有限自动机:Deterministic

FiniteAutomaton,DFA非确定有限自动机:NondeterministicFinite

Automaton,NFA1.确定有限自动机(DFA)确定有限自动机可表示为一个五元组,,f,s0,Z),其中记为DFA

Md

=(S,(1)S是有限状态集;(2)

是有穷字母表;(3)f

是一个从S×到S的单值映射,如f(si,a)=sj,

其中si,sj

S,

a

;s0是唯一初态,

s0

S;Z

是一个终态集,

Z

S右图所示DFA可表示为Md=(S,

,f,s0,Z),其中S={s1,

s2,

s3,

s4}={a,

b,

c}f是S×到S的单值映射:f(s1,a)=s2,

f(s1,b)=s3f(s1,

c)=s4s0=

s1Z={s2,

s3,

s4}s1s2s3s4cba2.非确定有限自动机(NFA)非确定有限自动机Mn也可表示为一个,

f,

Q,

Z),五元组,记为NFA

Mn=(S,其中(1)S,

,Z的意义与DFA相同;(2)f是从S×*到S的子集的映射;(3)

Q

是一个非空初态集,

Q

SDFA和NFA的主要区别:1>DFA只有一个初态,而NFA可有若干个初态;2>DFA的状态转换函数f是一个单值函数,而NFA的状态转换函数f是一个多值函数,即NFA中f(si,a)={若干状态},这表示由当前状态和当前输入字符不能唯一确定下一状态,即同一状态对同一输入字符可有不同的输出边。右图所示NFA表示为:Mn=(S,

,

f,

Q,

Z),

其中S={s1,

s2,

s3,

s4}={a,

c}f是S×*到S子集的映射:1

1

2

3f(s

,a)={s

,

s

,

s

}f(s1,c)={s4

}Q

={s1}Z

={s2,

s3,

s4}as1s2s3s4caa3.状态转换图与状态转换矩阵DFA和NFA都可用状态转换图表示。假定DFA有m个状态、n个输入符,则

其状态转换图含有m个状态,每个状态最多有n条输出边,

每条边用

中的一个字符作标记,

整个图有一个初态和若干个终态。假定NFA有m个状态、n个输入字,

则其状态转换图含有m个状态,每个状态最多有n条输出边,每条边用*中的一个字作标记,整个图有若干个初态和若干个终态。DFA和NFA也可用状态转换矩阵表示,其中行表示状态,列表示输入符,矩阵元素表示f(si,a)的值。例2.4

DFA

Md=({s0,s1,s2},{a,b},

f,

s0,{s2}),其中f(s0,a)=s1,f(s0,b)=s2,f(s1,a)=s1f(s1,b)=s2,

f(s2,a)=s2,

f(s2,b)=s1试给出Md的状态转换图与状态转换矩阵.解:状态转换图:as1s0abbas22b状态转换矩阵:字符状态s0a

bs1

s2112ss2ss2ss1例2.5

NFAMn=({s0,s1,s2},{a,b},f,{s0,s2},{s1}),其中f(s0,a)={s2},f(s0,b)={s0,s1},f(s1,af(s1,b)={s2},f(s2,a)=

,f(s2,b)={s1}试给出Mn的状态转换图与状态转换矩阵状态a

b{s2}

{s0,s1}s0s1s2Φ

{s2}Φ

{s1}解:

状态转换s2图21

:

状字态符转换矩阵:s0s2bbb

ba对于FA

M,

若存在一条从初态到终态的通路,

该通路上有向边所标识的字符依次连接得到字符串 ,

则称

可为FA

M所接受或识别。FA

M所能识别的字符串的集合称为

FA

M所识别的语言,记为L(M)。对于任意的FA

M和FA

M

,若L(M)=L(M

),

则称M与M

等价。2.4

正规式到有限自动机的构造由正规式与FA的等价性知:若R是上的一个正规式,则必存在NFA

M,使得L(M)=L(R),反之亦然。2.4.1 由正规式构造等价的NFA

M由正规式构造NFA

M的方法:(1)把正规式R表示为拓广转换图X

Y2R(2)利用下述三条转换规则构造NFA

Msir1|r2r12rr1r2sj

sisjsjsjsksir1r2sir1*si

sjr1sj

sisj

si

skr1si

sj

sir1

r1把正规式R转换为NFA

M的步骤:

(1)把R表示为拓广转换图,其中X为初态,Y为终态;(2)逐步运用三条转换规则不断加入新结点,

直至每条有向边上仅标识

的一个字母或

为止。例2.6

构造正规式b*(d|ad)(b|ab)+对应的NFA。解:(1)用R+=RR*把正规式改造为

b*(d|ad)(b|ab)(b|ab)*(2)逐步运用三条转换规则构造其

NFA

M如下:b*(d|ad)(b|ab)(b|ab)*XYd|adb*b|ababaddb|abbb41235Xb4d26b3b5781ad

a

babXX13

(b|ab)*2YYY基本概念:_CLOSURE(I)的定义:对于FA

M的任一状态子集I,若si∈I,

则si∈

_CLOSURE(I);若si∈I,

则从si出发经过

所能到达的状态sj

属于

_CLOSURE(I)2.4.2

NFA

M的确定化(2)Ia的定义:对于FA

M的任一状态子集I,若a是Σ中的一个字符,则定义Ia=

_CLOSURE(J),其中J是从I中状态出发经过a所能到达的所有状态的集合。例2.7

下图中取I={1,2},求从状态I出发经有向边a所能到达的状态集J和_CLOSURE(J)。a1524a6378aJ

={5,

4,

3}_CLOSURE(J)={5,6,2,

4,7,

3,8}Ia

={5,6,2,

4,7,

3,8}2.用子集法对NFA确定化的方法:(1)构造一张状态转换表,

其第1列为状态子集I,

每个输入符a对应表中一列Ia;(2)表的第1行第1列为

_CLOSURE(Q),

其中Q为初始状态集;(3)根据第1列中的状态集I,对每个输入符

a求Ia,并记入Ia列中。若此Ia不同于第1列已存在的所有状态子集,则将其顺序加入空行中的第1列。重复(3)直至对每个I及a均已求得

Ia,且无新的状态子集Ia加入第1列为止;重命名第1列的每个状态子集,

所得状态转换矩阵对应于与NFA

M等价的DFA

M"。例2.8正规式(a|b)*(aa|bb)(a|b)*的NFA

M如下,试将其确定化为DFA

M"。34251X6abba

ababY2解:用子集法将上述NFA

M确定化为:IIaIb{X,1,2}{1,2,3}{1,2,4}{1,2,3}

{1,2,3,5,6,Y}

{1,2,4}{1,2,4}

{1,2,3}

{1,2,4,5,6,Y}{1,2,3,5,6,Y}{1,2,3,5,6,Y}{1,2,4,6,Y}{1,2,4,5,6,Y}{1,2,3,6,Y}{1,2,4,5,6,Y}{1,2,4,5,6,Y}{1,2,4,6,Y}

{1,2,3,6,Y}{1,2,3,6,Y}{1,2,3,5,6,Y}{1,2,4,6,Y}3425Xa1bababa6bY2Sab012132214335464564635重命名为:a3252426212ab0

b

aababba

abb于是得到对应的DFA如下:Sab012132214335464564635NFA确定化所得的DFA可能含有多余的状态,需要化简。DFA

M的化简是指寻找一个状态数比M少的DFA

M ,

使得L(M)=L(M

)。化简后的DFA

M 满足下述条件:没有多余的状态;状态集中没有相互等价的状态2.4.3

DFA

M的化简两个状态相互等价:对于给定的DFA

M,

假定状态s1,s2∈S且s1≠s2,

若从s1出发能识别出字符串

而停于终态,

则从s2出发也能识别出

而停于终态;

反之,

若从s2出发能识别出

而停于终态,

则从s1出发也能识别出

而停于终态,

则称s1和s2等价,

否则称s1和s2是可区分的。DFA

M的状态最小化过程:是指将DFA

M的状态集分割成一些不相交的子集,使得任意两个不同的子集其状态是可区分的,而同一子集中的任意两个状态是等价的。然后,从每个子集中选出一种状态,同时消去其它等价状态,得到最简的

DFA

M"且L(M)=L(M")。DFA

M的化简方法:首先将DFA

M的状态集S中的终态

与非终态分开,形成两个子集,得到基本划分。对当前已划分出的I(1),I(2),…,I(m)子集,看每个I(i)是否能进一步划分。对某个I(i)={s1,s2,…,sk},若存在输入a字符a

使得I

(i)不全包含在当前划分的某个子集I(j)中,即跨越两个子集,则将I(i)一分为二。例如,下图中先将状态集S划分为终态集{3,4,5,6}和非终态集{0,1,2}。因{0,1,2}a={1,3}不全包含于{3,4,5,6}或{0,1,2},故划分为{0,2}和{1}。a32

5242

6212考虑{0,1,2}:0abb

aababba

abb(3)重复(2),直到每个子集均不能再分。不能再分是指子集要么仅有一个状态,要么有多个状态但这些状态不可区分。(a)无需划分(b)需划分s4s3s3s1s2aaaas1s2如何进行子集的划分呢?假定当前子集I(i)={s1,s2,…},其中s1和s2经过有向边a分别到达状态t1和t2,而t1和t2分属于当前已划出的两个不同子集I(j)和I(k),则应将I(i)分为两部分:I(i1)={s

|

s∈I(i)且s经有向边a到达t1}I(i2)=I(i)−I(i1)由于t1和t2是可区分的,因此I(i1)中状态与I(i2)中状态可区分。当子集个数不再增加时,得到一个最终划分。对于最终划分的每个子集,选取一个状态作为代表,形成新的DFA。例如,I(i)={s1,s2,s3}若选s1作为I(i)的代表,则原来指向s2和s3的有向边均改为指向新DFA中的s1。若

I(i)中含原初态,则s1为新初态;若I(i)中含原终态,则s1为新终态。例2.9

化简由例2.8得到的DFA。a32

5212

42

620abb

aab

abba

abb解:(1)将状态集S划分为终态集{3,4,5,6}和非终态集{0,1,2}。(2)考虑{0,1,2}:因{0,2,1}a={1,3}不全包含于{3,4,5,6}或{0,1,2},故划分为{0,2}和{1}。b不全包含于已划分出的某个子集,故划分为{0}和{2}。(4)考虑{3,4,5,6}:{3,4,5,6}a={3,6}包含于{3,4,5,6}{3,4,5,6}b={4,5}包含于{3,4,5,6}故不需划分。(5)按顺序把状态子集{0},{1},{2},{3,4,5,6}重命名为0,1,2,3,得化简后的DFA

M"":526212(3)考虑{0,2}:因{0,2}={2,4},0abb

aa

a

32bbbaaab42b333103aab2bSab012132213b

aabX1Y2例2.10

试用DFA的等价性证明正规式(a|b)*与(a*b*)*等价。解:(1)正规式(a|b)*对应的NFA如下:ab2.4.4 正规式到FA构造示例用子集法确定化得如下转换表:I{X,1,Y}Ia{1,Y}Ib{1,Y}{1,Y}{1,Y}{1,Y}Sab011111重命名转换表得:X1Y2ab0ab1ab0b于是得到DFA如下:a化简:首先将状态集划分为终态集{0,1}因{0,1}a={1}{0,1}b={1}{0,1},{0,1},故不需再划分。因此,最简DFA如下:I

Ia{X,1,2,3,Y

}{2,3,1,Y

}{2,3,1,Y}

{2,3,1,Y}Ib{2,3,1,Y}{2,3,1,Y}(2)(a*b*)*对应的NFA如图所示:a

b2

3X

1

Y2用子集法将NFA确定化得转换表:Sab011111重命名得状态转换矩阵:由于(a|b)*和(a*b*)*对应的状态转换矩阵相同,故二者等价。例2.11

C语言可接受的合法文件名为device:

name.extension其中device:和.extension可省。假定

device,name和extension都是字母串,长度不限但至少为1,试画出识别文件名的DFA

M。解:

所求正规式为(cc*:|

)cc*(.cc*|

)解:

所求正规式为(cc*:|

)cc*(.cc*|

)相应的NFA

M如下图所示:X24cc

1

:cc

3

·cc

Y用子集法确定化,并重命名:IIcI:I.Sc:

.{X,2}{1,3,Y}--01-

-{1,3,Y}{1,3,Y}{2}{4}112

3{2}{3,Y}--24-

-{4}{Y}--35-

-{3,Y}{3,Y}--44-

3{Y}{Y}--55-

-X1234:·ccccccY0352cc12：c2

c

42c·

·于是得到DFA如下:c最后对DFA化简,化简后仍为上图。例2.12

某高级程序语言无符号数的正规式为digit+(.digit+)?(e(+|−)?digit+)其中digit表示数字,()?表示()中内容可有可无,试给出其DFA

M。解:用d代表digit,其正规式为dd*

(.dd*|

)

(e(+|−|

)dd*)|

)相应的NFA如下所示:XY21234d5d·dde-dd+dd*

(.dd*|

)

(e(+|−|

)dd*)|

)II±IdI.IeS±d

.

e{X}-{1,3,Y}--0-1

-

-{1,3,Y}

-

{1,3,Y}{2}

{4,5}1-123{2}

-

{3,Y}-

-2-4--{4,5}

{5}

{Y}-

-356--{3,Y}

-

{3,Y}-

{4,5}4-4-3{5}

-

{Y}-

-5-6--{Y}

-

{Y}-

-6-6--用子集法将NFA

M确定化,并重命名.XY2234d15d·dde-dd+012

352

42

62ddedddd

d-+·

e于是得到下图所示的DFA

M":说明:状态5和状态6面对下一输入符的状态相同,但状态5为非终态,状态6为终态,故上述

DFA已为最简。S

±0

-1

-d11.-2e-32

-4--3

56--4

-4-35

-6--6

-6--例2.13

构造一DFA,

它接收 ={a,b}上所有满足下述条件的字符串:

该字符串中的每个a都有至少一个b直接跟在其后。解:所求正规式为b*(abb*)*,相应的

NFA

M如下图所示:XY212babb*XY21b342abbb*(abb*)*I{X,1,2,Y}Ia{3}Ib{1,2,Y}S0a1b2{3}-{4,2,Y}1-3{1,2,Y}{3}{1,2,Y}212{4,2,Y}{3}{4,2,Y}313用子集法将NFA

M确定化,然后重命名。20232321abaab2bb于是得到DFA

M"如下:S

a

b0

1

21

-

32

1

23

1

320bb1a用DFA

M的化简方法得到最终划分:{0,2,3},{1}重命名后得到化简的DFA

M""如下:从FA

M到正规式的转换规则如下:sir