第3章-自动机基础

第3章自动机基础自动机是一种语言模型，是语言的一种识别工具，其中的

有限自动机(FiniteAutomata)FA被用来处理正规语言，后者是编译程序设计中词法分析的对象。3.1正规语言及其描述方法3.2有限自动机的定义与分类3.3有限自动机的等价转换3.4有限自动机的实现3.5正规语言描述方法间的相互转换3.1正规语言及其描述方法

【定义】正规语言是指由正规文法定义的语言；程序设计语言中的单词，大都属于此种语言。正规语言有三种等价的表示方法：

(1)正规文法(2)正规式(3)有限自动机正规文法仅有三种形式的产生式：

(1)A->aB(2)A->a(3)A->【例3.1】G(Z)：A->aA|∵A=>;A=>aA=>aaA=>aaaA=>…=>an,n≥0∴L(G)={an|n≥0}正规文法正规语言※正规语言判定示例:【例3.2】L1={ambn|m≥0,n≥1},正规语言?

∵可由正规文法定义：

G1(S):S->aS|bA;A->bA|∴L1是正规语言。

【例3.3】L2={(ab)n|n≥1},正规语言?

∵可由正规文法定义：

G2(S):S->aA;A->bB;B->aA|∴L2是正规语言。

【例3.4】L3={anbn|n≥0},正规语言?

∵不能由正规文法定义(正规文法无法描述a和b数 量上相等！)：

∴

L3不是正规语言！

3.1.1正规语言的另外两种表示方法Ⅰ.正规式表示法：

※正规式是指由字母表中的符号，通过以下三种运算(也可以使用圆括号)连接起来构成的表达式e：闭包(*，+)连接

(.)或(|)

※设val(e),L(e)分别表示正规式

e的值和语言，则：

L(e)={x|x=val(e)}即正规式表示的语言是该正规式所有值的集合。正规式

L3={abnc,bn

|n≥0}，

L2={(ab)n|n≥1}，e2=(ab)+e3=ab*c|b*

L1={ambn|m≥0,n≥1}，e1=a*b+Ⅱ.有限自动机表示法：

L3={abnc

,bn|n≥0}L2={(ab)n|n≥1}

L1={ambn|m≥0,n≥1}+①②b-ab+①②③b-aa①②③④+-abcbb--FA1:FA2:FA3:※初看起来，有限自动机是带标记的有向图！3.1.1正规语言的另外两种表示方法

{1,2,3,4}—状态集;

其中：+(开始状态)；

-(结束状态){a,b,c}—字母表；

δ(1,a)=2—

变换

(或);…(表示1状态遇符号a变到2状态,…)；※有限自动机表示法说明：

①②aL3={abnc

,bn|n≥0}①②③④+-abcbb--

一个FA，若存在一条从某开始状态

i到某结束状态j

的通路，且这条通路上所有边的标记连成的符号串为，则就是一个句子；所有这样的的集合，就是该FA表示的语言。【图符说明】：【运行机制】：FA:e=

ab*c|b*

G(S):S->aA|bB|

，A->bA|c

，B->

bB|※正规语言的三种表示法综合示例：【例3.5】L={abnc,bn|n≥0},∑={a,b,c}；

【注】凡是能由上述三种方法中的一种表示的语言，一定是正规语言；反之，凡是不能由上述三种方法表示的语言，一定不是正规语言。1.正规文法描述：

2.正规式描述:3.有限自动机描述：①②③④+-abcbb--

3.2.1有限自动机的定义状态i

遇符号a时变换为状态

j

3.2有限自动机的定义和分类

变换(二元函数);Q(有限状态集);ija或【定义】有限自动机是一种数学模型，用于描述正规语言,可定义为五元组：

FA=(Q,∑,S,F,)

(i,a)=j其中：i,j∈Q,a∈∑+{};F(结束状态集,FQ);S(开始状态集,SQ);∑(字母表);即：L(FA)={x|i

j,x∈∑*,i∈S,j∈F}

FA存在一条从某初始状态i

到某结束状态j

的连续变换，且每次变换(=>)的边标记连成的符号串恰好为x；称x为FA接受，否则拒绝。令L(FA)为自动机FA所描述的正规语言；则则L(FA)的生成(或识别)过程如下所示：如右图有限自动机：

3.2.2有限自动机所描述的语言=>

x①②③④+-abcbb--设

x=a1a2…an，ai∈∑+{}a1=>i1ia2=>i2an=>j…则有即：含义是:

※L(FA)的生成(或识别)过程示例：①②③④+-abcbb--Ⅰ.第一条通路：FA1=>b④①+①+=>a②=>b②=>c③①+=>a②=>b②=>b②=>c③…Ⅱ.第二条通路：FA2①+=>①=>a②=>c③①+=>b④=>b④①+…∴L(FA)={abnc,bn|n≥0}∴L(FA1)={abnc|n≥0}∴L(FA2)={bn|n≥0}因而接受空串的

FA的典型特征！【例3.6】有限自动机：FA=(Q,∑,S,F,)

其中:Q={1,2,3,4},∑={a,b,c},S={1,2},F={3,4}

FA

的两种表现形式：⑴状态转换图:

3.2.3有限自动机的两种表现形式：δ(1,a)=2;δ(1,b)=4;δ(2,b)=2;δ(2,c)=3;δ(2,)=3;δ(4,b)=4;⑵变换表:※变换表结构：行(状态)，列(符号)，表项(变换后状态)①②③④+-abcbb-+4332421234abc+--+开始状态结束状态

【例3.7】A={abnc,(ab)n|n≥0}二:变换函数不单值(如一:开始状态不唯一,不好用!(1,a)=(2|4)),也不好用！

3.2.4有限自动机的分类方法一：联合式方法二：组合式1方法三：组合式2①②③+abc-④⑤+ab-比较之：①②③+abc-④⑤ab-的有限自动机构造：三:带有边，还是不好用!有好用的吗?!？①②③+abc-④ab-【例3.7】构造正规语言①②③+abc-④a⑤ba--

3.2.4有限自动机的分类【有限自动机分类】1.确定的有限自动机(DFA)特征：①开始状态唯一;②变换函数单值;③不带边。2.非确定的有限自动机(NFA)(1)带有边的非确定的有限自动机(NFA)(2)不带有边的非确定的有限自动机(NFA)--不能全部满足上述特征者！

※确定的有限自动机如右图所示：①②③+abb-b④c⑤⑥⑦b-aa--ccDFA:

A={abnc,(ab)n|n≥0}3.3有限自动机的等价转换※有限自动机的等价转换,主要包含两个内容：(1)有限自动机的确定化(NFA=>DFA);(2)有限自动机的最小化(DFA=>最小的DFA);非确定机(NFA)较易构造，但不好用！确定机(DFA)较难构造，但好用！

任何一非确定机NFA，皆可通过有效算法把其转化为等价的确定机DFA（二者描述的语言相同）。有限自动机的最小化,又称有限自动机的化简；是指：对给定的确定机DFA1,构造另一个确定机DFA2,使得L(DFA1)=L(DFA2),且DFA2的状态最少。

ab*,b+,L(FA2)={abn,bn|n≥0}

【定义1】设有两个有限自动机FA1和FA2，若L(FA1)=L(FA2)则称FA1与FA2等价，记作FA1FA2。

3.3.1有限自动机的等价Ⅰ.两个自动机的等价：①②③+ab-bFA2FA1∵L(FA1)=L(FA2)①②③+ab-bb---∴FA1FA2※四条通路，分别接受：

ab+,ab*,b+,L(FA1)={abn,bn|n≥0}※二条通路，分别接受：Ⅱ.两个状态的等价：

【定义2】设i和j为FA的两个状态，若把其看作初态，二者接受的符号串集合相同，则有ij(等价)。

3.3.1有限自动机的等价【例2】FA2①②③+abc-【例1】FA1:①②+abc-【注】如何判断两个状态的等价性？稍后再讨论。24？35？45？判断等价性：23？√∵2,3节点构成闭路

∴2,3等价；可合而为一×××a②③-④⑤ba-a(3)对边，按通路逆向逐一进行：3.3.2有限自动机的确定化算法Ⅰ.消除

边算法(

NFA=>

或DFA):NFA(1)若存在闭路，则把闭路上各节点合而为一：②abc-③④②abc-(2)

标记隐含的开始态和结束态：开始态的通路上的节点：+结束态逆向通路上节点：-①删除一个边；同时②引进新边：凡由原边终点发出的边，也要由其始点发出。(4)重复步骤(3)，直到再无边为止。①②+cb-b③++-②ab③⑤bcc∴{am,ambcn,amcn|m≥0,n≥1}L()=NFA(2)

标记隐含的开始态和结束态：L(NFA)=?※消除边算法示例：【例3.8】考查NFA：

①②③+ab④c-(1)

闭路上的节点等价（）,可合而为一；①②(3)

逆序逐一删除边，同时引进新边：②③ab④c-+-+①③ab④c-+c-+①③ab④c-+cc-+NFA+++②-③+，④+，3.3.2有限自动机的确定化算法(续1)Ⅱ.把化为DFA算法(=>DFA):NFANFA(2)

按的变换函数实施变换：NFA({qi1,…qin

}

,ak)=(qi1,ak)∪…∪(qin,ak)={qj1,…qjn}(3)若{qj1,…qjn}

未作为状态行标记，则作新行标记；a1a2a3…{q01,…q0n}(4)重复步骤(2)(3)，直到不再出现新状态集为止；(5)标记DFA的开始态和结束态：第一行{q01,…q0n}，(右侧)标记+

；凡是状态行中含有的结束状态者，(右侧)标记-

【注】必要时，新产生的DFA可用状态图表示。NFA字母表中符号开始态集NFA(1)构造DFA的变换表(框架)：{…}※确定化示例：NFA①②③+abc-④⑤+ab-【例3.9】联合式自动机NFA:※确定化过程:DFA:cbaD{3}F{2}E{5}C{2,4}G{4}E{5}D{3}F{2}F{2}E{5}G{4}D{3}D{3}C{2,4}B{2,5}B{2,5}+----ABCEFGD+-acbabcc-bba--【注】A,B,C,…状态集的代码A{1,4}※NFA确定化练习1.消除边练习2.确定化练习NFA1.消除边练习的答案2.确定化练习的答案NFA※NFA确定化练习01{1}{2}{2}{3}{3}{3}{4,5,6}{4,5,6}{3}{7}{7}{3}3.3.3有限自动机的最小化算法

最小有限自动机，是指满足下述条件的确定有限自动机：(1)没有无用状态(无用状态已删除)；(2)没有等价状态(等价状态已合并)。Ⅰ.删除无用状态算法

【定义】无用状态是指自动机从开始态出发，对任何符号串都不能到达的状态。【判别算法】构造有用状态集Qus(1)设q0

为开始态，则令q0∈Qus；(2)若qi∈Qus

且有(qi,a)=qj

则令qj∈Qus

；(3)重复执行(2)，直到Qus不再增大为止。(4)从状态集Q中，删除不在Qus中的所有状态。3.3.3有限自动机的最小化算法(续1)Ⅱ.合并等价状态算法【原理】两个状态i,j等价，当且仅当满足下面两个条件：①必须同是结束态，或同不是结束态；②对所有字母表上符号，状态i,j必变换到等价状态。【例】把下述自动机最小化：(1)初分成两个不等价子集：Q1={1,2},Q2={3}(2)还能分成不等价子集吗？∵(1,a)=2,(2,a)=2又(1,b)=3,(2,b)=3①③②+--babaa∴1≡2(等价)合并后的最小自动机①③+-aba3.3.3有限自动机的最小化算法(续2)Ⅱ.合并等价状态算法(1)初始，把状态集Q划分成两个不等价子集:Q1(结束状态集)，Q2(非结束状态集)；(2)把每个Qi再划分成不同的子集，条件是：

对同一Qi中两个状态i和j，若对字母表中的某个符号，变换到已划分的不同的状态集中，则i和j应分离:(3)重复步骤(2)，直到再不能划分为止；(4)合并最终划分的每个子集中的各状态(合而为一)。如(i,a)∈Qm,(j,a)∈Qn

且m≠n---划分不等价状态集※有限自动机化简示例【例3.10】化简下述DFA:(1)删除无用状态：

动态构造DFA变换表，即从开始状态1出发，把变换后的状态填入表项，并同时作为新行标记；如此下去，直到再不出现新状态为止。未出现的状态，就是无用的状态。【注】DFA中的状态2，8被删除!4647375644513361ba+---②③①+⑦-⑥-⑤-bababab④a⑧baaabaDFA的变换表：※有限自动机化简示例(续1)4647375644513361ba+---DFA:(2)合并等价状态:①令QNE={{1,3,4},{5,6,7}}②取{1,3,4}：即QNE={{1},{3,4},{5,6,7}}③取{3,4}：∵

(3,a)=1,(4,a)=4∴划分Q1={3},Q2={4}即QNE={{1},{3},{4},{5,6,7}}④取{5,6,7}:同理，可划分成Q1={5},Q2={6,7}；最后：QNE={{1},{3},{4},{5},{6,7}}不等价集∵

(1,a)=6,({3,4},a)={1,4}∴划分成Q1={1},Q2={3,4}※有限自动机化简示例(续2)4647375644513361ba+---DFA:合并等价状态:{6,7}46365644513361ba+--③①+⑥-⑤-babb④abaaa

6替换7最小的DFA!※有限自动机化简练习删除无用状态合并等价状态(3)令getchar(ch)为读符号函数。3.4有限自动机的实现

用计算机完成有限自动机的功能，其核心是“变换”的实现技术。这里介绍的是把变换表按某种方式存储起来，作为知识源来识别单词，实现机制是：

控制程序变换表+【三点说明】(1)假定自动机只作为识别器，即对待识别的符号串：仅回答是(接受)或否(拒绝)。(2)为便于处理，可令#

作为待识别的符号串的后继符。为此，扩展自动机如下：③①+⑥⑤-a④-b-##……ok

4ok

5…………

6

3

1#ba+--空则no3.4.1控制程序设计开始结束state=1getchar(ch)查变换表：(state,ch)=?

=空

=ok回答:yes回答:noynystate=n开始状态1赋给变量state从输入串中读取一符号到变量ch

变量state重新被赋值为变换后的状态！n…②①3.4.2变换表存储结构设计变换表的存储结构可选择下述两种方式之一：(1)二维数组，其下标是(状态，输入符号)；※为了适应不同编码语言的需要，状态和输入符号可采取相应的编码形式；通常，使用连续的正整数：0,1,2,3,…。(2)压缩变换表，方法是把每个状态行作为子表，状态为索引，并把错误的输入符号合并在一起，如：no…⑧b⑤ano…②f④e…no…⑨y①x索引表(其他)--错误符号。状态变换子表④③②①※有限自动机实现示例【例3.11】有限自动机DFA:③①+②④ab-#abcdno②b③ano④dno②c④b③anook#压缩变换表输入串aacd#识别过程：备注变换剩余chstate3acd#a1接受ok#44#d22d#c33cd#a3索引表3.5正规语言描述方法间的相互转换

正规语言有三种等价的表示方法：

(1)正规文法(2)正规式(3)有限自动机

我们以有限自动机为核心，介绍彼此间的转换关系：

Ⅰ.正规文法<=>DFA设G(Z)=(VN,VT,Z,P),DFA=(Q,∑,S,F,)则有：∑VT(A,a)=BA->aB(A,a)=B(结束态)A->aS(开始态)Z(开始符号)QVNDFA正规文法A->A(结束态)有时需要增加一个结束状态Z->aZ|bA|,A->bA|dB,B->※正规文法与DFA间转换示例：【例3.12】自动机=>正规文法:①②③abcd+-DFA:令Z-①,A-②,B-③则有正规文法Z->aA|cB,A-