3.4 3.4 正规语言正规语言描述方法描述方法间的间的相互转换相互转换 众所周知众所周知，正规语言正规语言有三种等价的表示方法：有三种等价的表示方法： 正规文法正规文法 正规式正规式 有限自动机有限自动机 我们以我们以有限自动机有限自动机为核心，介绍彼此间的转换关系：为核心，介绍彼此间的转换关系： . . 正规文法正规文法 DFA DFA设设 G(Z)=(VG(Z)=(VN N,V,VT T,Z,P), DFA=(Q,s,F,Z,P), DFA=(Q,s,F, ) )则有：则有：DFADFA正规文法正规文法 ( (字符字符集集) ) V VT T ( (终结符终结符集集) ) (A,a)=B(A,a)=BA - A - aBaB (A,a)=B(A,a)=B(结束态结束态) )A - aA - a S(S(开始状态开始状态) ) Z(Z(开始符号开始符号) ) Q(Q(状态状态集集) ) V VN N( ( 非终结符非终结符集集) )A - A - A A( (结束态结束态) ) Z-Z-aZ|bAaZ|bA| | , A- , A-bA|dBbA|dB ,B- ,B- 正规文法正规文法 与与 DFADFA间转换示例：间转换示例：【例例3.163.16】 自动机自动机 = = 正规文法正规文法: :ab bcd d+ +- -DFADFA: :令令 Z=, A=, B=Z=, A=, B=则有则有 正规文法正规文法Z - Z - aAaA【例例3.173.17】正规文法正规文法 = = 自动机自动机, , 并求并求 L(G)L(G): :G(Z): Z-G(Z): Z-aZ|bAaZ|bA| | ,A- ,A-bA|dbA|d A-d A-d 可变换为可变换为 G(Z) ( G(Z) ( 与与 G(Z)G(Z)等价等价 ): ): 令令 -Z, -A, -B-Z, -A, -B对应的对应的DFADFAb ba ad d+ +- - -b b则则 L(G)=L(G)= , ,a am mb bn nd|m0,n0d|m0,n0G(Z):G(Z):| | cBcB , A -, A -bAbA | dB| dB , B- , B- A-dB, B-A-dB, B- s sf fe e+ +- -. . 正规式正规式 DFA DFA设设 e e 为正规式为正规式 , DFA=(Q,s,F, DFA=(Q,s,F, ) ) 转换机制转换机制： e = DFA e = DFA 分解过程分解过程 ( ( 其逆过程为合成过程其逆过程为合成过程) )：则有：则有：合成合成分解分解i ij je e1 1| |e e2 2i ij je e1 1. .e e2 2i ij je e* *i ij je e2 2e e1 1i ij je e1 1k ke e2 2i ij je ek k 实践实践中，可简中，可简化为其中化为其中一种：一种：i ie ej j j je ei i e ei ie ej j或或或或或或 正规式正规式 与与 DFADFA间转换示例：间转换示例：【例例3.183.18】正规式正规式 = = 自动机自动机 设设 e = ae = a* *b|bcb|bc* *则：则：a a* *b bbcbc* *+ +- -a a* *c c* *+ +- -b bb b+ +- -a aa aa aa ac c+ +- -b bb bb b- -+ +a aa ac cA A+ +B Bb bb bD D- -C CE Ec c- - -等价等价! !a a c c+ +- -b bb b b bc c+ +- -b bb b + +- -确定化确定化2 2DFA:DFA:确定化确定化1 1 b bc ca aA1,2A1,2 + +D9D9C3,9C3,9 B2B2B2B2D9D9E3E3C3,9C3,9 B2B2E3E3E3E3- - - - 令令 getchar(chgetchar(ch) ) 读符号函数。读符号函数。3.5 3.5 有限自动机的实现问题有限自动机的实现问题 用计算机完成有限自动机的功能，用计算机完成有限自动机的功能，其核心是“变换”的实现技术。这里介绍的是把变换表按某种方式存贮起来，作为知识源，实现机制是： 【三点说明三点说明】 假定自动机只作为假定自动机只作为识别器识别器，即，即 对对待识别的待识别的符号串符号串： 仅回答仅回答 是是( (接受接受) )或或 否否( (拒绝拒绝) )。 为便于处理为便于处理, ,可令可令为此，扩展自动机如下：为此，扩展自动机如下：okok 4 4okok 5 5 6 6 3 3 1 1 b b a a+ +- - -空空 则则 nono控制程序控制程序 变换表变换表 + + +- -a a- -b b- -作为作为待识别的待识别的符号串符号串的泛指的泛指后继符后继符。3.5.1 3.5.1 控制程序设计控制程序设计开始开始结束结束state:=1state:=1getchar(chgetchar(ch) )查变换表：查变换表： ( (state,chstate,ch)= )= ? ? = = =ok=ok回答回答:ok:ok回答回答:no:noy yn ny ystate:= state:= n n 开始状态开始状态1 1赋赋给变量给变量 statestate 从输入串中从输入串中读取一符号到读取一符号到变量变量 chch 变量变量 state state 重新被赋值！重新被赋值！ n3.5.2 3.5.2 变换表存贮结构设计变换表存贮结构设计变换表的存贮结构可选择下述两种方式之一：变换表的存贮结构可选择下述两种方式之一： 二维数组二维数组 ，其下标是，其下标是( (状态，输入符号）；状态，输入符号）； 为了适应不同编码语言的需要，状态和输入符为了适应不同编码语言的需要，状态和输入符号可采取相应的编码形式；通常，使用连续的正整号可采取相应的编码形式；通常，使用连续的正整数：数：0,1,2,3,0,1,2,3,。 压缩变换表压缩变换表，方法是把每个状态行作为，方法是把每个状态行作为子表，状态为子表，状态为索引，索引，并把并把错误的输入符号合并在一起错误的输入符号合并在一起, ,如：如：nobanofenoyx索引表索引表 ( (其他其他)-)-错误符号。错误符号。状状态态变换子表变换子表c ca a3 3有限自动机实现示例：有限自动机实现示例：【例例3.193.19】 有限自动机有限自动机DFA: DFA: + +a ab b- -# #a ab bc cd d nonob ba a nonod dnono c cb ba a nonookok# #压缩变换表压缩变换表输入串输入串 aacdaacd# # 识别过程：识别过程：索引表索引表备注备注变换变换剩余剩余chchstatestate3 3acdacd# #a a1 1接受接受okok# #4 44 4# #d d2 22 2d#d#3 33 3cdcd# #练习题练习题: :【习题习题3.73.7】已知正规式已知正规式 ，试转换为自动机和正规文法：，试转换为自动机和正规文法： e1=(e1=(abab) )* * ; e2=(a|b); e2=(a|b)* * . .【习题习题3.83.8】已知符号串集合，构造正规式、自动机和正规文已知符号串集合，构造正规式、自动机和正规文法：法：A= A= ,a,an n,ba,ban n|n1 |n1 【习题习题3.93.9】已知自动机已知自动机DFA:DFA:ab bb bc cc cb bb b- -+ +- - 扩展扩展DFA(DFA(加入结束标记加入结束标记#),#),构造压缩变换表；构造压缩变换表； 根据实现算法，写出识别根据实现算法，写出识别 abbcabbc# #的过程。的过程。【习题习题3.103.10】P64_11,12P64_11,12谢谢收看！