自动机与形式语言第三章epsilon-NFA课件.ppt
2023/3/28,1,RG,RE,-NFA,NFA,DFA,正则语言(RL),2023/3/28,2,3.4 带空移动的有穷状态自动机,接受语言0n1m2k|n，m，k0的NFA,3,允许带 输入的状态跳转这些状态跳转可以同时进行，无需输入字符方便构造，更加“智能”，但也只接收RL,3.4 带空移动的有穷状态自动机,2023/3/28,4,3.4 带空移动的有穷状态自动机,接受语言0n1m2k|n，m，k0的NFA是否可以构造成下图所示的“-NFA”？,其构造显然比图1-13所示的NFA更容易。当然还希望它们是等价的。,5,例子:-NFA,2023/3/28,6,3.4 带空移动的有穷状态自动机,带空移动的不确定的有穷状态自动机(non-deterministic finite automaton with-moves,-NFA)M=(Q，q0，F)，Q、q0、F的意义同DFA。：Q()2Q,2023/3/28,7,3.4 带空移动的有穷状态自动机,非空移动(q，a)Q(q，a)=p1，p2，pm表示M在状态q读入字符a，可以选择地将状态变成p1、p2、或者pm，并将读头向右移动一个带方格而指向输入字符串的下一个字符。,2023/3/28,8,3.4 带空移动的有穷状态自动机,空移动qQ(q，)=p1，p2，pm表示M在状态q不读入任何字符，可以选择地将状态变成p1、p2、或者pm。也可以叫做M在状态q做一个空移动(又可以称为移动)，并且选择地将状态变成p1、p2、或者pm。,9,-NFA状态的闭包,-CLOSURE(q)=从状态q出发，跟随标记的弧所能到达的状态的集合。例:-CLOSURE(A)=A;-CLOSURE(E)=B,C,D,E.状态集合的闭包-CLOSURE(P)=集合P中所有元素的闭包的集合 例:-CLOSURE(A,E)=A,B,C,D,E;,2023/3/28,10,3.4 带空移动的有穷状态自动机,-CLOSURE(q)=p|从q到p有一条标记为的路。,11,拓展的,基础:(q,)=-CLOSURE(q).归纳:(q,wa)计算为：从(q,w)=S出发；对于S中所有元素p，计算-CLOSURE(p,a)的并集。结论:(q,w)是从q出发，沿着标记为w的路径所有能到达的状态的集合。,2023/3/28,12,3.4 带空移动的有穷状态自动机,13,例子:拓展的,(A,)=-CLOSURE(A)=A.(A,0)=-CLOSURE(E)=B,C,D,E.(A,01)=-CLOSURE(C,D)=C,D.-NFA 的语言是所有w的集合，(q0,w)包含接受状态。,2023/3/28,14,3.4 带空移动的有穷状态自动机,对任意(P，a)2 Q。,2023/3/28,15,3.4 带空移动的有穷状态自动机,在-NFA中，对任意a，qQ，,需要严格区分。,2023/3/28,16,q0,q1,q2,q1,q2,q1,q2,2023/3/28,17,3.4 带空移动的有穷状态自动机,M接受(识别)的语言 对于x*，仅当,时，称x被M接受。,18,NFA,-NFA等价,所有 NFA 都是-NFA.仅仅不包含带的状态转换要证明等价性，需证明对于任意的-NFA，能构建一个接收相同语言的NFA方法：把transition跟“真实”的状态转换结合起来,19,消除-Transition,接受w后,a,a,a,跳转,状态q,(q,wa)=,-CLOSURE(),p1,p2,pn,P,a,2023/3/28,20,3.4 带空移动的有穷状态自动机,定理 3-2-NFA与NFA等价。证明：设有-NFA M1=(Q，1，q0，F)(1)构造与之等价的NFA M2。取NFA M2=(Q，2，q0，F2)Fq0如果F-CLOSURE(q0)F2=F如果F-CLOSURE(q0)=,2023/3/28,21,3.4 带空移动的有穷状态自动机,与上图-NFA等价的NFA。,2023/3/28,22,3.5 FA是正则语言的识别器 3.5.1 FA与右线性文法,DFA M=(Q，q0，F)，处理句子a1a2an的特性。M按照句子a1a2an中字符的出现顺序，从开始状态q0开始，依次处理字符a1、a2、an，在这个处理过程中，每处理一的字符进入一个状态，最后停止在某个终止状态。,2023/3/28,23,3.5.1 FA与右线性文法,它每次处理且仅处理一个字符：第i步处理输入字符ai。对应于使用(q，a)=p的状态转移函数的处理，相当于是在状态q完成对a的处理，然后由p接下去实现对后续字符的处理。当(q，a)=pF，且a是输入串的最后一个字符时，M完成对此输入串的处理。,2023/3/28,24,3.5.1 FA与右线性文法,A0 a1A1对应产生式A0 a1A1 a1a2A2对应产生式A1 a2A2 a1a2an-1An-1对应产生式An-2 an-1An-1 a1a2an-1an对应产生式An-1 an,2023/3/28,25,3.5.1 FA与右线性文法,q0 a1a2an-1ana1q1 a2an-1an对应(q0，a1)=q1a1a2q2an-1an对应(q1，a2)=q2a1a2an-1qn-1an对应(qn-2，an-1)=qn-1a1a2an-1anqn对应(qn-1，an)=qn,2023/3/28,26,3.5.1 FA与右线性文法,其中qn为M的终止状态。考虑根据a1、a2、an，让A0与q0对应、A1与q1对应、A2与q2对应、An-2与qn-2对应、An-1与qn-1对应。这样，就有希望得到满足定理2-4-1的正则文法的推导与DFA的互相模拟的方式。,2023/3/28,27,3.5.1 FA与右线性文法,定理 3-3 FA接受的语言是正则语言。证明：(1)构造。基本思想是让RG的派生对应DFA的移动。设DFA M=(Q，q0，F)，取右线性文法 G=(Q，P，q0)，P=qap|(q，a)=pqa|(q，a)=pF,2023/3/28,28,3.5.1 FA与右线性文法,（2）证明 L(G)=L(M)-。对于a1a2an-1an+，q0+a1a2an-1an q0 a1q1，q1 a2q2，qn-2 an-1qn-1，qn-1 anP(q0，a1)=q1，(q1，a2)=q2，(qn-2，an-1)=qn-1，(qn-1，an)=qn，且qnF(q0，a1a2an-1an)=qnF a1a2an-1anL(M),2023/3/28,29,3.5.1 FA与右线性文法,（3）关于句子。如果q0F，则L(M)，L(G)=L(M)。如果q0F，则由定理2-6和定理2-7，存在正则文法G，使得L(G)=L(G)=L(M)。综上所述，对于任意DFA M，存在正则文法G，使得L(G)=L(M)。定理得证。,2023/3/28,30,3.5.1 FA与右线性文法,例：与下图所给DFA等价的正则文法qs0|0q0|1q1q00|0q0|1q1q10q2|1|1q0q20q1|1q2,2023/3/28,31,3.5.1 FA与右线性文法,例：与下图所给的DFA等价的正则文法 q00q1|1qt|2qtq10q1|1q2|2qtq20qt|1q2|2q3|2 q30qt|1qt|2q3|2qt 0qt|1qt|2qt,2023/3/28,32,3.5.1 FA与右线性文法,定理3-4 正则语言可以由FA接受。证明：（1）构造。基本思想：让FA模拟RG的派生。设G=(V，T，P，S)，且L(G)，取FA M=(VZ，T，S，Z)，ZV。,2023/3/28,33,3.5.1 FA与右线性文法,对(a，A)TV B|AaBPZ如果AaP(A，a)=B|AaBP如果AaP 用B(A，a)与产生式AaB对应 用Z(A，a)与产生式Aa对应。,2023/3/28,34,3.5.1 FA与右线性文法,（2）证明L(M)=L(G)对于a1a2an-1anT+，a1a2an-1anL(G)S+a1a2an-1an Sa1A1 a1a2A2 a1a2an-1An-1 a1a2an-1an Sa1A1，A1a2A2，An-2an-1An-1，An-1anP,2023/3/28,35,3.5.1 FA与右线性文法,A1(S，a1)，A2(A1，a2)，An-1(An-2，an-1)，Z(An-1，an)Z(S，a1a2an-1an)a1a2an-1anL(M)对于，按照定理2-5和定理2-6处理。,2023/3/28,36,3.5.1 FA与右线性文法,例 3-10 构造与所给正则文法等价的FA：G1：E0A|1B A1|1C B0|0C C0B|1A,2023/3/28,37,3.5.1 FA与右线性文法,(E，0)=A对应E0A(E，1)=B对应E1B(A，1)=Z,C对应A1|1C(B，0)=Z,C对应B0|0C(C，0)=B对应C0B(C，1)=A对应C1A,2023/3/28,38,3.5.1 FA与右线性文法,2023/3/28,39,3.5.1 FA与右线性文法,推论3-1 FA与正则文法等价。证明：根据定理3-3和定理3-4即可得到。,2023/3/28,40,3.5.1 FA与左线性文法,按照推导来说，句子a1a2an-1an中的字符被推导出的先后顺序正好与它们在句子中出现的顺序相反；而按照归约来看，它们被归约成语法变量的顺序则正好与它们在句子中出现的顺序相同：a1，a2，an-1，an。可见，归约过程与FA处理句子字符的顺序是一致的，所以可考虑依照“归约”来研究FA的构造。,2023/3/28,41,3.5.1 FA与左线性文法,对于形如Aa的产生式：在推导中，一旦使用了这样的产生式，句型就变成了句子，而且a是该句子的第一个字符；按“归约”理解，对句子的第1个字符，根据形如Aa的产生式进行归约。对应到FA中，FA从开始状态出发，读到句子的第一个字符a，应将它“归约”为A。我们如果考虑用语法变量对应FA的状态，那么，此时我们需要引入一个开始状态，比如说：Z。这样，对应形如Aa的产生式，可以定义A(Z，a)。,2023/3/28,42,3.5.1 FA与左线性文法,按照上面的分析，对应于形如ABa的产生式：FA应该在状态B读入a时，将状态转换到A。也可以理解为：在状态B，FA已经将当前句子的、处理过的前缀“归约”成了B，在此时它读入a时，要将Ba归约成A，因此，它进入状态A。,2023/3/28,43,3.5.1 FA与左线性文法,按照“归约”的说法，如果一个句子是文法G产生的语言的合法句子，它最终应该被归约成文法G的开始符号。所以，G的开始符号对应的状态就是相应的FA的终止状态。如何解决好开始符号只有一个，而DFA的终止状态可以有多个的问题。,2023/3/28,44,3.5.1 FA与左线性文法,例如：对文法G2：EA0|B1A1|C1B0|C0CB0|A1,对应(A，0)=E(B，1)=E(Z，1)=A(C，1)=A(Z，0)=B(C，0)=B(B，0)=C(A，1)=C,2023/3/28,45,3.5.1 FA与左线性文法,G2：EA0|B1A1|C1B0|C0CB0|A1,2023/3/28,46,3.5.1 FA与左线性文法,定理3-5 左线性文法与FA等价。,2023/3/28,47,3.6 FA的一些变形,3.6.1 双向有穷状态自动机 确定的双向有穷状态自动机(two-way deterministic finite automaton，2DFA)M=(Q，q0，F)Q、q0、F的意义同DFA。,2023/3/28,48,3.6.1 双向有穷状态自动机,：QQL，R，S，对(q，a)Q 如果(q，a)=p，L，它表示M在状态q读入字符a，将状态变成p，并将读头向左移动一个带方格而指向输入字符串的前一个字符。如果(q，a)=p，R，它表示M在状态q读入字符a，将状态变成p，并将读头向右移动一个带方格而指向输入字符串中下一个字符。如果(q，a)=p，S，它表示M在状态q读入字符a，将状态变成p，读头保持在原位不动。,2023/3/28,49,3.6.1 双向有穷状态自动机,M接受的语言 L(M)=x|q0 x*xp且pF 是2DFA接受的语言。定理3-6 2DFA与FA等价。,2023/3/28,50,3.6.1 双向有穷状态自动机,不确定的双向有穷状态自动机(two-way nondeterministic finite automaton，2NFA)M=(Q，q0，F)Q、q0、F的意义同DFA。：Q2QL，R，S。,2023/3/28,51,3.6.1 双向有穷状态自动机,(q，a)=(p1，D1)(p2，D2)，(pm,Dm)表示M在状态q读入字符a，可以选择地将状态变成p1同时按D1实现对读头的移动、或者将状态变成p2同时按D2实现对读头的移动、或者将状态变成pm同时按Dm实现对读头的移动。其中D1，D2，DmL，R，S，表示的意义与2DFA的定义表示的意义相同。,2023/3/28,52,3.6.1 双向有穷状态自动机,定理3-7 2NFA与FA等价。,2023/3/28,53,3.6.2 带输出的FA,Moore机 M=(Q，q0)Q、q0、的意义同DFA。输出字母表(output alphabet)。：Q为输出函数。对qQ，(q)=a表示M在状态q时输出a。,2023/3/28,54,3.6.2 带输出的FA,对于a1a2an-1an*，如果(q0，a1)=q1，(q1，a2)=q2，(qn-2，an-1)=qn-1，(qn-1，an)=qn，则M的输出为(q0)(q1)(qn-1),2023/3/28,55,3.6.2 带输出的FA,Mealy机 M=(Q，q0)输出字母表。：Q为输出函数。对(q，a)Q，(q，a)=d表示M在状态q读入字符a时输出d。,2023/3/28,56,3.6.2 带输出的FA,对于a1a2an-1an*，M的输出串为：(q0,a1)(q0,a1),a2)(q0，a1),a2),an)设(q0，a1)=q1，(q1，a2)=q2，(qn-2，an-1)=qn-1，(qn-1，an)=qn，则M的输出可以表示成：(q0，a1)(q1，a2)(qn-1，an),2023/3/28,57,3.6.2 带输出的FA,Moore机处理该串时每经过一个状态，就输出一个字符：输出字符和状态一一对应；Mealy机处理该串时的每一个移动输出一个字符：输出字符和移动一一对应。,2023/3/28,58,3.6.2 带输出的FA,定理3-8 Moore机与Mealy机等价。,2023/3/28,59,3.7 小结,本章讨论正则语言的识别器FA。包括DFA、NFA、-NFA。RG与FA的等价性。简单介绍带输出的FA和双向FA。FA M是一个五元组，M=(Q，q0，F)，它可以用状态转移图表示。M接受的语言为x|x*且(q，x)F。如果L(M1)=L(M2)，则称M1与M2等价。FA的状态具有有穷的存储功能。这一特性可以用来构造接受一个给定语言的FA。,2023/3/28,60,3.7 小结,NFA允许M在一个状态下读入一个字符时选择地进入某一个状态，对于x*，如果(q0，x)F，则称x被M接受，如果(q0，x)F=，则称M不接受x。M接受的语言L(M)=x|x*且(q0，x)F。,2023/3/28,61,3.7 小结,-NFA是在NFA的基础上，允许直接根据当前状态变换到新的状态而不考虑输入带上的符号。对qQ，(q，)=p1，p2，pm表示M在状态q不读入任何字符，可以选择地将状态变成p1、p2、或者pm。这叫做M在状态q做一个空移动。NFA与DFA等价，-NFA与NFA等价，统称它们为FA。,2023/3/28,62,3.7 小结,根据需要，可以在FA中设置一种特殊的状态陷阱状态。但是，不可达状态却是应该无条件地删除的。FA是正则语言的识别模型。分别按照对推导和归约的模拟，可以证明FA和左线性文法、右线性文法等价。,2023/3/28,63,3.7 小结,2DFA是FA的又一种变形，它不仅允许读头向前移动，还允许读头向后移动。通过这种扩充，2DFA仍然与FA等价。Moore机和Mealy机是两种等价的带输出的FA，Moore机根据状态决定输出字符，Mealy机根据移动决定输出字符。,
