资源描述
,*,3.4,正规语言,描述方法,间的,相互转换,众所周知,，,正规语言,有三种等价的表示方法：,正规文法 正规式 有限自动机,我们以,有限自动机,为核心，介绍彼此间的转换关系：,.正规文法 DFA,设 G(Z)=(V,N,V,T,Z,P),DFA=(Q,s,F,),则有：,DFA,正规文法,(,字符,集),V,T,(,终结符,集),(A,a)=B,A-aB,(A,a)=B(,结束态,),A-a,S(,开始状态,),Z(,开始符号,),Q(,状态,集),V,N,(,非终结符,集),A-,A,(,结束态,),Z-aZ|bA|,A-bA|dB,B-,正规文法 与 DFA间转换示例：,【例3.16】,自动机=正规文法,:,a,b,c,d,+,-,DFA:,令 Z=,A=,B=,则有 正规文法,Z-aA,【例3.17】,正规文法=自动机,并求 L(G),:,G(Z):Z-aZ|bA|,A-bA|d,A-d 可变换为,G(Z)(与 G(Z)等价):,令-Z,-A,-B,对应的DFA,b,a,d,+,-,-,b,则 L(G)=,a,m,b,n,d|m0,n0,G(Z):,|cB,A-bA,|dB,B-,A-dB,B-,s,f,e,+,-,.正规式 DFA,设 e 为正规式,DFA=(Q,s,F,),转换机制,：,e=DFA 分解过程,(,其逆过程为合成过程),：,则有：,合成,分解,i,j,e,1,|,e,2,i,j,e,1,.,e,2,i,j,e,*,i,j,e,2,e,1,i,j,e,1,k,e,2,i,j,e,k,实践中，可简化为其中一种：,i,e,j,j,e,i,e,i,e,j,或,或,或,正规式 与 DFA间转换示例：,【例3.18】,正规式,=自动机,设,e=a,*,b|bc,*,则：,a,*,b,bc,*,+,-,a,*,c,*,+,-,b,b,+,-,a,a,a,a,c,+,-,b,b,b,-,+,a,a,c,A,+,B,b,b,D,-,C,E,c,-,-,等价!,a,c,+,-,b,b,b,c,+,-,b,b,+,-,确定化2,DFA:,确定化1,b,c,a,A1,2,+,D9,C3,9,B2,B2,D9,E3,C3,9,B2,E3,E3,-,-,-,令 getchar(ch)读符号函数。,3.5 有限自动机的实现问题,用计算机完成有限自动机的功能，,其核心是“,变换,”的实现技术。这里介绍的是把,变换表,按某种方式存贮起来，作为知识源，实现机制是：,【三点说明】,假定自动机只作为,识别器,，即,对,待识别的,符号串,：,仅回答,是,(接受)或,否,(拒绝)。,为便于处理,可令,为此，扩展自动机如下：,ok,4,ok,5,6,3,1,b,a,+,-,-,空 则 no,控制程序 变换表,+,+,-,a,-,b,-,作为,待识别的,符号串,的泛指,后继符,。,3.5.1 控制程序设计,开始,结束,state:=1,getchar(ch),查变换表：,(state,ch)=?,=,=ok,回答:ok,回答:no,y,n,y,state:=,n,开始状态1赋给变量 state,从输入串中读取一符号到变量 ch,变量 state 重新被赋值！,n,3.5.2 变换表存贮结构设计,变换表的存贮结构可选择下述两种方式之一：,二维数组,，其下标是(状态，输入符号）；,为了适应不同编码语言的需要，状态和输入符号可采取相应的编码形式；通常，使用连续的正整数：0,1,2,3,。,压缩变换表,，方法是把每个状态行作为,子表，状态为索引，,并把,错误的输入符号合并在一起,如：,no,b,a,no,f,e,no,y,x,索引表,(其他)-错误符号。,状态,变换子表,c,a,3,有限自动机实现示例：,【例3.19】有限自动机DFA:,+,a,b,-,#,a,b,c,d,no,b,a,no,d,no,c,b,a,no,ok,#,压缩变换表,输入串 aacd#识别过程：,索引表,备注,变换,剩余,ch,state,3,acd#,a,1,接受,ok,#,4,4,#,d,2,2,d#,3,3,cd#,练习题:,【习题3.7】已知正规式，试转换为自动机和正规文法：,e1=(ab),*,;e2=(a|b),*,.,【习题3.8】已知符号串集合，构造正规式、自动机和正规文法：,A=,a,n,ba,n,|n1,【习题3.9】已知自动机DFA:,a,b,b,c,c,b,b,-,+,-,扩展DFA(加入结束标记#),构造压缩变换表；,根据实现算法，写出识别 abbc#的过程。,【习题3.10】P64_11,12,谢谢收看！,再见,
展开阅读全文