RG、FA、RE等相互之间的转换

正则文法（RG）NFA正则表达式（RE）123456DFA最小化(MFA)实际问题一、概览1.对转换 函 关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函 数δ(A,t)=B，可写成一个产生式:A→tB算法:2.对可接受状态Z，增加一个产生式：Z→ε3.有限自动机的初态对应于文法的开始符号,有限自动机的字母表为文法的终结符号集。ABt（1）有限自动机正则文法例：给出如图NFA等价的正则文法G。ABCDstartaaabbbb【解】G=（{A，B，C，D}，{a，b}，P，A）其中P:A→aBA→bDB→bCC→aAC→bDC→εD→aBD→bDD→ε这是右线性正则文法!作业三（1）算法:①字母表与G的终结符号相同，即=VT。G的开始符号S是M的初始状态q0;②为G中的每个非终结符生成M的一个状态，再增加一个新状态Z,作为自动机M的终态，则Q=VN∪{Z}。③对G中的形如A→tB的产生式,其中t为终结符或ε,A和B为非终结符,构造M的一个转换函数f(A,t)=B④对G中的形如A→t的产生式,构造M的一个转换函数f(A,t)=Z（2）正则文法有限自动机【例】求与文法G[S]等价的NFAG[S]:S→aA|bB|εA→aB|bAB→aS|bA|εSZABstartaaabbbεε作业三（2）语法制导 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ：1.(a)对于正规式φ，所构造NFA:xy(b)对于正规式ε，所构造NFA:xyε(c)对于正规式a，a∈Σ，所构造NFA:xya（3）正规式有限自动机2.若s,t为Σ上的正规式,相应的NFA分别为N(s)和N(t);(a)对于正规式R=s|t，NFA(R)(b)对正规式R=st，NFA(R)N(s)N(t)εεεεxy或:N(s)xN(t)yxyN(s)N(t)εεε(c)对于正规式R=s*,NFA(R)(d)对R=(s),与R=S的NFA一样.xyN(s)εεεε例:为R=(a|b)*abb构造NFA,使得L(N)=L(R)从左到右分解R，令r1=a，第一个a，则有：23a令r2=b，则有：45b令r3=r1|r2，则有：164532abεεεε令r4=r3，则有：*164532abεεεε0ε7εεε作业三（1）令r10=r4r9则最终得到NFAM:164532abεεεε0ε7εεε1089abb令r5=a,令r6=b令r7=b令r8=r5r6令r9=r8r7则有910b87ba分解R的方法有很多种，所以结果并不唯一。阅读P49作业三（3）P56第2-24（1）将正规式：(a|b)*a(a|b)转换为最简的确定有限自动机。【解】先转换为NFA：qs012qZaεεa,babIIaIb{qs,0,1}{0,1,2}{0,1}{0,1,2}{0,1,2,qz}{0,1,qz}{0,1}{0,1,2}{0,1}{0,1,2,qz}{0,1,2,qz}{0,1,qz}{0,1,qz}{0,1,2}{0,1}NFA的确定化表Qab0121342123*344*12重命名后的DFAQab0101232*233*10化简后的DFA（4）有限自动机正规式阅读P50【例】03214starta,ba,ba,bbbaa解:(1)加x,yx03412yεεεaa,ba,ba,babb作业三（4）x03412yεεεaa,ba,ba,babb(2)消除（合并）M中的所有结点a|bx024yεεεaabba|ba|bx0yaa(a|b)*bb(a|b)*a|bεxy(a|b)*(aa|bb)(a|b)*利用以下转换规则,直至只剩下一个开始符号定义的产生式,并且产生式的右部不含非终结符.规则规则1规则2规则3文法产生式正规式A→xB,B→yA→xA|yA→x,A→yA=xyA=x*yA=x|y【例】有文法G[s]S→aA|a,A→aA|dA|a|d【解】:由A→aA|dA|a|d，得：A→(aA|dA)|(a|d)A→(a|d)A|(a|d)由规则2得:A=(a|d)*(a|d)代入S产生式:S→a(a|d)*(a|d)|a于是，有:S=a((a|d)*(a|d)|ε)（5）正则文法正规式算法:（1）对任何正规式r，选择一个非终结符S作为识别符号，并产生产生式：S→r（2）若x，y是正规式，则对形如A→xy的产生式重写为：A→xB，B→y其中B为新的非终结符，B∈VN（3）同样:对于A→x*yA→xA，A→yA→x|yA→x，A→y【例】将R=a(a|d)*转换成相应的正则文法。【解】（1）S→a(a|d)*（2）S→aAA→(a|d)*（3）S→aAA→(a|d)AA→ε（4）S→aAA→aA|dAA→ε（6）正规式正则文法左线性文法和右线性文法之间存在一定关系。一个左线性文法GL存在一个等价的右线性文法GR。一个右线性文法GR存在一个等价的左线性文法GL。可见，GL和GR是等价的，也就是说，给定一个右线性文法可以构造对应的左线性文法。同样，给一个左线性文法也可以构造一个右线性文法。注意：左线性和右线性文法的关系它们之间的等价关系：上述等价关系规定开始符号S不能出现在规则左部。例：设左线性文法Ｇ＝（ＶＮ，ＶＴ，S，Ｐ），其中:ＶＮ={A,B,S}ＶＴ={0,1}P:S∷＝A0|B1A∷＝0|1B∷＝0|1则L(GL)={00,01,10,11}。由等价关系得:则右线性文法Ｇ＝（ＶＮ，ＶＴ，Ｐ，S）,其中:ＶＮ={A,B,S}ＶＴ={0,1}P:S∷＝0A|1A|0B|1BA∷＝0B∷＝1则L(GR)={00,01,10,11}。所以L(GL)=L(GR),说明左线性文法和右线性文法是等价的。非确定的有限自动机NFA与确定的有限自动机DFA从功能上来说是等价的，即：NFAM’DFAM构造成一个使得L(M)=L(M’)二、NFA的确定化λ（ε）合并符号合并转换思想：转换函数δ初态NFAM(S,∑,δ,S0,F)S×∑→S的子集多值映射S0S非空初态集DFAM(S,∑,δ,s0,F)S×∑→S单值映射s0∈S唯一的初态NFA允许ε边出现λ（ε）合并：如果有S1→S2,则把S2状态合并到S1状态。εNFA到DFA的区别：例1：NFA转换成DFA(符号合并)例2： 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 一个DFA，其输入字母表是{0,1}，它能接受以0开始，以1结尾的所有序列。aa3cb012a01,2cb30,10ZCSABε1ε解：①根据题意，得出相应的正规式：0(0|1)*1②得状态转换图(NFA)如下：01stateDFAstateSS,ABCSABCS,ABCS,ABCABCBCBCZABC,BC,BCZS,ABC,BC,BCZBCBCBCZBC,BCZS,ABC,BC,BCZBCZBCBCZBCZS,ABC,BC,BCZ③NFA确定为DFA过程：DFA的初态（为NFA的初始状态经过ε合并后的状态的并集）例：δ(S,ε)=;DFA的其它状态（为NFA的状态经过输入符号后产生的状态，再经过ε合并后的状态的并集）例：求δ(S,0)=？δ(S,0)=A;δ(A,ε)=B;δ(B,ε)=C;δ(C,ε)=；DFA的终态（为所有含有NFA的终态的状态）0,10ZCSABε1ε01stateDFAstateSS,ABCSABCS,ABCS,ABCABCBCBCZABC,BC,BCZS,ABC,BC,BCZBCBCBCZBC,BCZS,ABC,BC,BCZBCZBCBCZBCZS,ABC,BC,BCZNFA确定化过程：(初态、其它状态、终态)0,10ZCSABε1ε③δ(A,0)=;δ(B,0)=B;δ(B,ε)=C;δ(C,ε)=;δ(C,0)=;δ(ABC,0)①δ(S,ε)=;初态②δ(S,0)=A;δ(A,ε)=B;δ(B,ε)=C;δ(C,ε)=；δ(S,0)得状态转换图(DFA)如下：000SCA101B1000SBCZABC101BC1在DFA中，所有含有NFA的终态的状态作为DFA的终态DFAM=({S,A,B,C},{0,1},δ,S,{C})其中δ如上（不可省略）定义1：集合I的ε-闭包：令I是一个状态集的子集，定义ε-closure（I）为：1）若s∈I，则s∈ε-closure（I）；2）若s∈I，则从s出发经过任意条ε弧能够到达的任何状态都属于ε-closure（I）。状态集ε-closure（I）称为I的ε-闭包为了使得NFA确定化，我们首先给出两个定义：56432aεaaε1例：如图所示的状态图：令I={1}，求ε-closure（I）=？根据定义：ε-closure（I）={1，3}——J是从状态子集I中的每个状态出发，经过标记为a的弧而达到的状态集合.——Ia是状态子集,其元素为J中的状态，加上从J中每一个状态出发通过ε弧到达的状态定义2:令I是NFAM’的状态集的一个子集,a∈Σ定义:Ia=ε-closure(J)其中J=∪δ(s,a)S∈I56432aεaaε1例：令I={1}，求Ia=?Ia=ε-closure(J)=ε-closure(δ(1，a)）=ε-closure({2，4}）={2，4，6}例：有NFAM，求DFAM’。a1234startabaccεI=ε-closure({1})={1,4}Ia=ε-closure(δ(1,a)∪δ(4,a))=ε-closure({2,3}∪φ）=ε-closure({2,3})={2,3}Ib=ε-closure(δ(1,b)∪δ(4,b))=ε-closure(φ）=φIc=ε-closure(δ(1,c)∪δ(4,c))=φI={2,3},Ia={2},Ib={4},Ic={3,4}…IIaIbIc{1,4}{2,3}φφ{2,3}{2}{4}{3,4}{2}{2}{4}φ{4}φφφ{3,4}φφ{3,4}初态startIIaIbIc{1,4}{2,3}φφ{2,3}{2}{4}{3,4}{2}{2}{4}φ{4}φφφ{3,4}φφ{3,4}符号状态abc02341221________3344DFAM’状态转换矩阵将求得的状态转换矩阵重新编号01423{1,4}{2,3}{4}{2}acabbc{3,4}“对于任一个DFA，存在一个唯一的状态最少的等价的DFA”一个有限自动机是化简的它没有多余状态并且它的状态中没有两个是互相等价的。一个有限自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有限自动机。三、DFA的化简定义：(1)有限自动机的多余状态：从该自动机的开始状态出发，任何输入串也不能到达那个状态。01s0s1s2s3s5s7s1s5s1s2s2s5s5s1s1s3s0s1例:s0为初始状态画状态图可以看出s4,s6,s8为不可达状态应该消除01s0s1s2s3s4s5s6s7s8s1s5s7s2s2s5s5s7s5s6s1s3s8s0s0s1s3s6(2)等价状态状态s和t的等价条件是:1)一致性条件：状态s和t必须同时为可接受状态或不接受状态.2)蔓延性条件：对于所有输入符号,状态s和t必须转换到等价的状态里.对于所有输入符号c，Ic(s)=Ic(t)，即状态s、t对于c具有相同的后继，则称s，t是等价的。（任何有后继的状态和任何无后继的状态一定不等价）有限自动机的状态s和t不等价,称这两个状态是可区别的。“分割法”：把一个DFA(不含多余状态)的状态分割成一些不相关的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的.例1:最小化5724361srartaaaaaaabbbbbbb状态集的划分将所有DFA的终态与其它状态划分成两个子集G1,G2;分别从两个子集G1,G2中寻找等价状态进行化简。解:(一)区分终态与非终态12345663731546737414212ab567374142ab123463731546123区号区号5724361srartaaaaaaabbbbbbb将所有DFA的终态与其它状态划分成两个子集123456637315467374142ab12431243123456637315467374142ab5区号区号12345ab5214355231155243aaaaabbbbb567374142ab123463731546123区号将区号代替状态号得:例2：设计一个DFA，其输入字母表是{0,1}，它能接受以0开始，以1结尾的所有序列。——化简01SABCABCBCBCZBCBCBCZBCZBCBCZ①S,ABC,BCBCZ②SABC,BC01SABCABCABCBCZBCZABCBCZDFAM=({S,ABC,BCZ},{0,1},δ,S,{BCZ})其中δ如上(不可省略)00SBCZABC011005311240,110,10,101011233423235343423345235235345345235345011233423235343423235235235235化简后的DFA:例3：试求与下图所示NFA等价的化简了的DFA。a*|b*(ba)*bbaa*εεbb*b723εεa86145εεbεεba例4：试构造与正规式R=(a*|b*)b(ba)*等价的状态最少的DFA。ab12342434568242456834568345678568734567868345678768687注：状态从1~8标注NFA确定为DFA: