自动机与形式语言第三章epsilon-NFA介绍学习资料.ppt

《自动机与形式语言第三章epsilon-NFA介绍学习资料.ppt》由会员分享，可在线阅读，更多相关《自动机与形式语言第三章epsilon-NFA介绍学习资料.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、自动机与形式语言第三章epsilon-NFA介绍允许带允许带 输入输入的状态跳转的状态跳转这些状态跳转可以同时进行，无需输入字这些状态跳转可以同时进行，无需输入字符符方便构造，更加方便构造，更加“智能智能”，但也，但也只接收只接收RL3.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 23.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 接受语言接受语言0n1m2k|n，m，k0的的NFA是否可是否可以构造成下图所示的以构造成下图所示的“-NFA”？其构造显然比图其构造显然比图1-13所示的所示的NFA更容易。更容易。当然还希望它们是等价的。当然还希望它们是等价的。2022/12/

2、163例子例子:-NFACEFABD111000 0 1 A E B B C DC D D E F B,CF D *43.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 带空移动的不确定的有穷状态自动机带空移动的不确定的有穷状态自动机(non-deterministic finite automaton with-moves,-NFA)M=(Q，q0，F)，Q、q0、F的意义同的意义同DFA。：Q()2Q 2022/12/1653.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 非空移动非空移动(q，a)Q(q，a)=p1，p2，pm表示表示M在状态在状态q读入字符读入字符a，可以

3、选择地，可以选择地将状态变成将状态变成p1、p2、或者或者pm，并将读，并将读头向右移动一个带方格而指向输入字符头向右移动一个带方格而指向输入字符串的下一个字符。串的下一个字符。2022/12/1663.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 空移动空移动 qQ(q，)=p1，p2，pm表示表示M在状态在状态q不读入任何字符，可以选不读入任何字符，可以选择地将状态变成择地将状态变成p1、p2、或者或者pm。也。也可以叫做可以叫做M在状态在状态q做一个空移动做一个空移动(又可以又可以称为称为移动移动)，并且选择地将状态变成，并且选择地将状态变成p1、p2、或者或者pm。2022/1

4、2/167-NFA状态的闭包-CLOSURE(q)=从状态q出发，跟随标记的弧所能到达的状态的集合。例:-CLOSURE(A)=A;-CLOSURE(E)=B,C,D,E.状态集合的闭包-CLOSURE(P)=集合P中所有元素的闭包的集合 例:-CLOSURE(A,E)=A,B,C,D,E;CEFABD11100083.4 带空移动的有穷状态自动机带空移动的有穷状态自动机-CLOSURE(q)=p|从从q到到p有一条标记为有一条标记为的路的路。2022/12/169拓展的拓展的基础:(q,)=-CLOSURE(q).归纳:(q,wa)计算为：1.从 (q,w)=S出发；2.对于S中所有元素p，

5、计算-CLOSURE (p,a)的并集。结论:(q,w)是从q出发，沿着标记为w的路径所有能到达的状态的集合。103.4 带空移动的有穷状态自动机带空移动的有穷状态自动机2022/12/1611例子:拓展的 (A,)=-CLOSURE(A)=A.(A,0)=-CLOSURE(E)=B,C,D,E.(A,01)=-CLOSURE(C,D)=C,D.-NFA 的语言是所有w的集合，(q0,w)包含接受状态。CEFABD11100012 3.4 带空移动的有穷状态自动机带空移动的有穷状态自动机对任意对任意(P，a)2Q。2022/12/16133.4 带空移动的有穷状态自动机带空移动的有穷状态自动机

6、在在-NFA中，对任意中，对任意a，qQ，需要严格区分。需要严格区分。2022/12/1614状状态态012012q0q1q0q0,q1,q2q2q1q2q1q1,q2q2q2q2q2q2q0,q1,q2q1,q2q1,q22022/12/16153.4 带空移动的有穷状态自动机带空移动的有穷状态自动机M接受接受(识别识别)的语言的语言 对于对于 x*，仅当，仅当 时，称时，称x被被M接受。接受。2022/12/1616NFA,-NFA等价所有 NFA 都是-NFA.仅仅不包含带的状态转换要证明等价性，需证明对于任意的-NFA，能构建一个接收相同语言的NFA方法：把transition跟“真实

7、”的状态转换结合起来17消除-Transition接受接受w后后aaa 跳转跳转状态q(q,wa)=-CLOSURE()p1p2pnPa183.4 带空移动的有穷状态自动机带空移动的有穷状态自动机定理定理 3-2-NFA与与NFA等价。等价。证明：设有证明：设有-NFA M1=(Q，1，q0，F)(1)构造与之等价的构造与之等价的NFAM2。取取NFA M2=(Q，2，q0，F2)Fq0如果如果F-CLOSURE(q0)F2=F如果如果F-CLOSURE(q0)=2022/12/16193.4 带空移动的有穷状态自动机带空移动的有穷状态自动机与上图与上图-NFA等价的等价的NFA。2022/1

8、2/16203.5 FA是正则语言的识别器是正则语言的识别器 3.5.1 FA与右线性文法与右线性文法 DFAM=(Q，q0，F)，处理句子，处理句子a1a2an的特性。的特性。M按照句子按照句子a1a2an中字符的出现顺序，中字符的出现顺序，从开始状态从开始状态q0开始，依次处理字符开始，依次处理字符a1、a2、an，在这个处理过程中，每处理一的字，在这个处理过程中，每处理一的字符进入一个状态，最后停止在某个终止状符进入一个状态，最后停止在某个终止状态。态。2022/12/16213.5.1 FA与右线性文法与右线性文法它它每每次次处处理理且且仅仅处处理理一一个个字字符符：第第i步步处处理理

9、输入字符输入字符ai。对对应应于于使使用用(q，a)=p的的状状态态转转移移函函数数的的处处理理，相相当当于于是是在在状状态态q完完成成对对a的的处处理理，然后由然后由p接下去实现对后续字符的处理。接下去实现对后续字符的处理。当当(q，a)=pF，且，且a是输入串的最后一是输入串的最后一个字符时，个字符时，M完成对此输入串的处理。完成对此输入串的处理。2022/12/16223.5.1 FA与右线性文法与右线性文法A0a1A1对应产生式对应产生式A0a1A1a1a2A2对应产生式对应产生式A1a2A2 a1a2an-1An-1对应产生式对应产生式An-2an-1An-1a1a2an-1an对应

10、产生式对应产生式An-1an2022/12/16233.5.1 FA与右线性文法与右线性文法q0a1a2an-1ana1q1a2an-1an对应对应(q0，a1)=q1a1a2q2an-1an对应对应(q1，a2)=q2a1a2an-1qn-1an对应对应(qn-2，an-1)=qn-1a1a2an-1anqn对应对应(qn-1，an)=qn 2022/12/16243.5.1 FA与右线性文法与右线性文法其中其中qn为为M的终止状态。考虑根据的终止状态。考虑根据a1、a2、an，让，让A0与与q0对应、对应、A1与与q1对应、对应、A2与与q2对应、对应、An-2与与qn-2对应、对应、An

11、-1与与qn-1对对应。这样，就有希望得到满足定理应。这样，就有希望得到满足定理2-4-1的的正则文法的推导与正则文法的推导与DFA的互相模拟的方式。的互相模拟的方式。2022/12/16253.5.1 FA与右线性文法与右线性文法定理定理 3-3FA接受的语言是正则语言。接受的语言是正则语言。证明：证明：(1)构造。构造。基本思想是让基本思想是让RG的派生对应的派生对应DFA的移动。的移动。设设DFAM=(Q，q0，F)，取右线性文法取右线性文法G=(Q，P，q0)，P=qap|(q，a)=pqa|(q，a)=pF2022/12/16263.5.1 FA与右线性文法与右线性文法（2）证明证明

12、L(G)=L(M)-。对于对于a1a2an-1an+，q0+a1a2an-1anq0a1q1，q1a2q2，qn-2an-1qn-1，qn-1anP(q0，a1)=q1，(q1，a2)=q2，(qn-2，an-1)=qn-1，(qn-1，an)=qn，且且qnF(q0，a1a2an-1an)=qnFa1a2an-1anL(M)2022/12/16273.5.1 FA与右线性文法与右线性文法（3）关于关于句子。句子。如果如果q0 F，则，则 L(M)，L(G)=L(M)。如如果果q0F，则则由由定定理理2-6和和定定理理2-7，存存在在正正则文法则文法G，使得，使得L(G)=L(G)=L(M)。

13、综上所述，对于任意综上所述，对于任意DFAM，存在正则文法，存在正则文法G，使得，使得L(G)=L(M)。定理得证。定理得证。2022/12/16283.5.1 FA与右线性文法与右线性文法例：例：与下图所给与下图所给DFA等价的正则文法等价的正则文法qs0|0q0|1q1q00|0q0|1q1q10q2|1|1q0q20q1|1q22022/12/16293.5.1 FA与右线性文法与右线性文法例：例：与下图所给的与下图所给的DFA等价的正则文法等价的正则文法 q00q1|1qt|2qtq10q1|1q2|2qtq20qt|1q2|2q3|2q30qt|1qt|2q3|2qt0qt|1qt|

14、2qt 2022/12/16303.5.1 FA与右线性文法与右线性文法定理定理3-4正则语言可以由正则语言可以由FA接受。接受。证明：证明：（1）构造。）构造。基本思想：让基本思想：让FA模拟模拟RG的派生。的派生。设设G=(V，T，P，S)，且，且 L(G)，取取FAM=(VZ，T，S，Z)，Z V。2022/12/16313.5.1 FA与右线性文法与右线性文法对对(a，A)TVB|AaBPZ如果如果AaP(A，a)=B|AaBP如果如果Aa P用用B(A，a)与产生式与产生式AaB对应对应用用Z(A，a)与产生式与产生式Aa对应。对应。2022/12/16323.5.1 FA与右线性文

15、法与右线性文法（2）证明证明L(M)=L(G)对于对于a1a2an-1anT+，a1a2an-1anL(G)S+a1a2an-1anSa1A1a1a2A2a1a2an-1An-1a1a2an-1anSa1A1，A1a2A2，An-2an-1An-1，An-1anP2022/12/16333.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处理。处理。2022/12/16343.5.1 FA与右线性文法与右线性

16、文法例例3-10构造与所给正则文法等价的构造与所给正则文法等价的FA：G1：E0A|1BA1|1CB0|0CC0B|1A 2022/12/16353.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对应对应C1A2022/12/16363.5.1 FA与右线性文法与右线性文法2022/12/16373.5.1 FA与右线性文法与右线性文法推论推论3-1FA与正则文法等价。与正则文法等价。证明：根据定理证明：根据定理3-3和定理和定理3-4

17、即可得到。即可得到。2022/12/16383.5.1 FA与左线性文法与左线性文法按照推导来说，句子按照推导来说，句子a1a2an-1an中的字符被中的字符被推导出的先后顺序正好与它们在句子中出推导出的先后顺序正好与它们在句子中出现的顺序相反；而按照归约来看，它们被现的顺序相反；而按照归约来看，它们被归约成语法变量的顺序则正好与它们在句归约成语法变量的顺序则正好与它们在句子中出现的顺序相同：子中出现的顺序相同：a1，a2，an-1，an。可见，归约过程与可见，归约过程与FA处理句子字符的顺序处理句子字符的顺序是一致的，所以可考虑依照是一致的，所以可考虑依照“归约归约”来研来研究究FA的构造。

18、的构造。2022/12/16393.5.1 FA与左线性文法与左线性文法对于形如对于形如Aa的产生式：在推导中，一旦的产生式：在推导中，一旦使用了这样的产生式，句型就变成了句子，使用了这样的产生式，句型就变成了句子，而且而且a是该句子的第一个字符；按是该句子的第一个字符；按“归约归约”理解，对句子的第理解，对句子的第1个字符，根据形如个字符，根据形如Aa的产生式进行归约。对应到的产生式进行归约。对应到FA中，中，FA从开从开始状态出发，读到句子的第一个字符始状态出发，读到句子的第一个字符a，应，应将它将它“归约归约”为为A。我们如果考虑用语法变。我们如果考虑用语法变量对应量对应FA的状态，那么

19、，此时我们需要引的状态，那么，此时我们需要引入一个开始状态，比如说：入一个开始状态，比如说：Z。这样，对应。这样，对应形如形如Aa的产生式，可以定义的产生式，可以定义A(Z，a)。2022/12/16403.5.1 FA与左线性文法与左线性文法按照上面的分析，对应于形如按照上面的分析，对应于形如ABa的产生的产生式：式：FA应该在状态应该在状态B读入读入a时，将状态转换时，将状态转换到到A。也可以理解为：在状态。也可以理解为：在状态B，FA已经将已经将当前句子的、处理过的前缀当前句子的、处理过的前缀“归约归约”成了成了B，在此时它读入，在此时它读入a时，要将时，要将Ba归约成归约成A，因，因此

20、，它进入状态此，它进入状态A。2022/12/16413.5.1 FA与左线性文法与左线性文法按照按照“归约归约”的说法，如果一个句子是文的说法，如果一个句子是文法法G产生的语言的合法句子，它最终应该被产生的语言的合法句子，它最终应该被归约成文法归约成文法G的开始符号。所以，的开始符号。所以，G的开始的开始符号对应的状态就是相应的符号对应的状态就是相应的FA的终止状态。的终止状态。如何解决好开始符号只有一个，而如何解决好开始符号只有一个，而DFADFA的终的终止状态可以有多个的问题。止状态可以有多个的问题。2022/12/16423.5.1 FA与左线性文法与左线性文法例如：对文法例如：对文法

21、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)=C2022/12/16433.5.1 FA与左线性文法与左线性文法G2：EA0|B1A1|C1B0|C0CB0|A1 2022/12/16443.5.1 FA与左线性文法与左线性文法 定理定理3-5 左线性文法与左线性文法与FA等价。等价。2022/12/16453.6 FA的一些变形的一些变形 3.6.1 双向有穷状态自动机双向有穷状态自动机 确定的双向有穷状态自动机确定的双向有穷状态自动机(two-way determin

22、istic finite automaton，2DFA)M=(Q，q0，F)Q、q0、F的意义同的意义同DFA。2022/12/16463.6.1 双向有穷状态自动机双向有穷状态自动机：QQL，R，S，对，对(q，a)Q 如果如果(q，a)=p，L，它表示，它表示M在状态在状态q读入读入字符字符a，将状态变成，将状态变成p，并将读头向左移动一个，并将读头向左移动一个带方格而指向输入字符串的前一个字符。带方格而指向输入字符串的前一个字符。如果如果(q，a)=p，R，它表示，它表示M在状态在状态q读入读入字符字符a，将状态变成，将状态变成p，并将读头向右移动一个，并将读头向右移动一个带方格而指向输

23、入字符串中下一个字符。带方格而指向输入字符串中下一个字符。如果如果(q，a)=p，S，它表示，它表示M在状态在状态q读入读入字符字符a，将状态变成，将状态变成p，读头保持在原位不动。，读头保持在原位不动。2022/12/16473.6.1 双向有穷状态自动机双向有穷状态自动机M接受的语言接受的语言 L(M)=x|q0 x*xp且且pF 是是2DFA接受的接受的语言。语言。定理定理3-6 2DFA与与FA等价。等价。2022/12/16483.6.1 双向有穷状态自动机双向有穷状态自动机不确定的双向有穷状态自动机不确定的双向有穷状态自动机(two-way nondeterministic fin

24、ite automaton，2NFA)M=(Q，q0，F)Q、q0、F的意义同的意义同DFA。：Q2QL，R，S。2022/12/16493.6.1 双向有穷状态自动机双向有穷状态自动机(q，a)=(p1，D1)(p2，D2)，(pm,Dm)表示表示M在状态在状态q读入字符读入字符a，可以选择地将，可以选择地将状态变成状态变成p1同时按同时按D1实现对读头的移动、或实现对读头的移动、或者将状态变成者将状态变成p2同时按同时按D2实现对读头的移动、实现对读头的移动、或者将状态变成或者将状态变成pm同时按同时按Dm实现对读实现对读头的移动。其中头的移动。其中D1，D2，DmL，R，S，表示的意义与

25、，表示的意义与2DFA2DFA的定义表示的意义的定义表示的意义相同相同。2022/12/16503.6.1 双向有穷状态自动机双向有穷状态自动机定理定理3-7 2NFA与与FA等价。等价。2022/12/16513.6.2 带输出的带输出的FA Moore机机 M=(Q，q0)Q、q0、的意义同的意义同DFA。输出字母表输出字母表(output alphabet)(output alphabet)。：Q为输出函数。对为输出函数。对 qQ，(q)=a表示表示M在状态在状态q时输出时输出a。2022/12/16523.6.2 带输出的带输出的FA 对于对于 a1a2an-1an*，如果，如果(q0

26、，a1)=q1，(q1，a2)=q2，(qn-2，an-1)=qn-1，(qn-1，an)=qn，则则M的输出为的输出为(q0)(q1)(qn-1)2022/12/16533.6.2 带输出的带输出的FA Mealy机机 M=(Q，q0)输出字母表。输出字母表。：Q为输出函数。对为输出函数。对(q，a)Q，(q，a)=d表示表示M在状态在状态q读入读入字符字符a时输出时输出d。2022/12/16543.6.2 带输出的带输出的FA 对于对于 a1a2an-1an*，M的输出串为：的输出串为：(q0,a1)(q0,a1),a2)(q0，a1),a2),an)设设(q0，a1)=q1，(q1，a

27、2)=q2，(qn-2，an-1)=qn-1，(qn-1，an)=qn，则则M的输出可以表示成：的输出可以表示成：(q0，a1)(q1，a2)(qn-1，an)2022/12/16553.6.2 带输出的带输出的FA Moore机机处处理理该该串串时时每每经经过过一一个个状状态态，就就输输出一个字符：输出字符和状态一一对应；出一个字符：输出字符和状态一一对应；Mealy机处理该串时的每一个移动输出一个机处理该串时的每一个移动输出一个字符：输出字符和移动一一对应。字符：输出字符和移动一一对应。2022/12/16563.6.2 带输出的带输出的FA 定理定理3-8Moore机与机与Mealy机等

28、价机等价。2022/12/16573.7 小结小结 本章讨论正则语言的识别器本章讨论正则语言的识别器FA。包括包括DFA、NFA、-NFA。RG与与FA的等的等价性。简单介绍带输出的价性。简单介绍带输出的FA和双向和双向FA。FAM是是一一个个五五元元组组，M=(Q，q0，F)，它可以用状态转移图表示。，它可以用状态转移图表示。M接接 受受 的的 语语 言言 为为 x|x*且且(q，x)F。如如果果L(M1)=L(M2)，则则称称M1与与M2等价。等价。FA的的状状态态具具有有有有穷穷的的存存储储功功能能。这这一一特特性可以用来构造接受一个给定语言的性可以用来构造接受一个给定语言的FA。202

29、2/12/16583.7 小结小结 NFA允许允许M在一个状态下读入一个字符在一个状态下读入一个字符时选择地进入某一个状态，对于时选择地进入某一个状态，对于 x*，如果如果(q0，x)F，则称，则称x被被M接受，接受，如果如果(q0，x)F=，则称，则称M不接受不接受x。M接受的语言接受的语言L(M)=x|x*且且(q0，x)F。2022/12/16593.7 小结小结-NFA是是在在NFA的的基基础础上上，允允许许直直接接根根据据当当前前状状态态变变换换到到新新的的状状态态而而不不考考虑虑输输入入带带上上的的符符号号。对对 qQ，(q，)=p1，p2，pm表表示示M在在状状态态q不不读读入入

30、任任何何字字符符，可可以以选选择择地地将将状状态态变变成成p1、p2、或或者者pm。这这叫叫做做M在状态在状态q做一个空移动。做一个空移动。NFA与与DFA等等价价，-NFA与与NFA等等价价，统统称它们为称它们为FA。2022/12/16603.7 小结小结 根根据据需需要要，可可以以在在FA中中设设置置一一种种特特殊殊的的状状态态陷陷阱阱状状态态。但但是是，不不可可达达状状态态却却是是应该无条件地删除的。应该无条件地删除的。FA是是正正则则语语言言的的识识别别模模型型。分分别别按按照照对对推推导导和和归归约约的的模模拟拟，可可以以证证明明FA和和左左线线性性文文法、右线性文法等价。法、右线

31、性文法等价。2022/12/16613.7 小结小结 2DFA是是FA的的又又一一种种变变形形，它它不不仅仅允允许许读读头头向向前前移移动动，还还允允许许读读头头向向后后移移动动。通通过过这种扩充，这种扩充，2DFA仍然与仍然与FA等价。等价。Moore机机和和Mealy机机是是两两种种等等价价的的带带输输出出的的FA，Moore机机根根据据状状态态决决定定输输出出字字符符，Mealy机根据移动决定输出字符。机根据移动决定输出字符。2022/12/1662此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢