自动机与形式语言第三章epsilon_NFA

1、2022-3-221RGRE-NFA NFADFA 正则语言正则语言 (RL)2022-3-2223.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 接受语言接受语言0n1m2k|n，m，k0的的NFA 3 允许带允许带 输入输入的状态跳转的状态跳转 这些状态跳转可以同时进行，无需输入字这些状态跳转可以同时进行，无需输入字符符 方便构造，更加方便构造，更加“智能智能”，但也，但也只接收只接收RL3.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 2022-3-2243.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 接受语言接受语言0n1m2k|n，m，k0的的NFA是否可是

2、否可以构造成下图所示的以构造成下图所示的“-NFA ”？ 其构造显然比图其构造显然比图1-13所示的所示的NFA更容易。更容易。当然还希望它们是等价的。当然还希望它们是等价的。5例子例子: -NFACEFABD111000 0 1 A E B B C DC D D E F B, CF D *2022-3-2263.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 带空移动的不确定的有穷状态自动机带空移动的不确定的有穷状态自动机(non-deterministic finite automaton with -moves,-NFA)M=(Q，q0，F)，Q、q0、F的意义同的意义同DFA。

3、：Q()2Q 2022-3-2273.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 非空移动非空移动 (q，a)Q (q，a)= p1，p2，pm 表示表示M在状态在状态q读入字符读入字符a，可以选择地，可以选择地将状态变成将状态变成p1、p2、或者或者pm ，并将读，并将读头向右移动一个带方格而指向输入字符头向右移动一个带方格而指向输入字符串的下一个字符。串的下一个字符。2022-3-2283.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 空移动空移动 qQ (q，)= p1，p2，pm 表示表示M在状态在状态q不读入任何字符，可以选不读入任何字符，可以选择地将状态变成择地将

4、状态变成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;CEFABD1110002022-3-22103.4 带空移动的有穷状态自动机带空移动

5、的有穷状态自动机 -CLOSURE(q)=p|从从q到到p有一条标记为有一条标记为的路的路。 PppCLOSUREPCLOSURE)()()2(11拓展的拓展的基础: (q, ) = -CLOSURE(q).归纳: (q, wa)计算为：从 (q, w) = S出发；对于S中所有元素p，计算 -CLOSURE (p, a) 的并集。1. 结论: (q, w) 是从q出发，沿着标记为w的路径所有能到达的状态的集合。2022-3-22123.4 带空移动的有穷状态自动机带空移动的有穷状态自动机)(),() 3(qCLOSUREq),(),(),(),(|)(),()4(wrrararpwqrpPP

6、CLOSUREwaq使得13例子:拓展的 (A, ) = -CLOSURE(A) = A. (A, 0) = -CLOSURE(E) = B, C, D, E. (A, 01) = -CLOSURE(C, D) = C, D. -NFA 的语言是所有w的集合， (q0, w) 包含接受状态。CEFABD1110002022-3-2214 3.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 对任意对任意(P，a)2 Q。 PqaqaP),(),()5(PqwqwP),(),()6(2022-3-22153.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 在在-NFA中，对任意中，对任

7、意a，qQ，),(),(aqaq需要严格区分。需要严格区分。2022-3-2216状状态态 012012q0 q1 q0q0,q1,q2q2q1 q2 q1q1,q2q2q2 q2q2q2q0,q1,q2q1,q2q1,q22022-3-22173.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 M接受接受(识别识别)的语言的语言 对于对于 x*，仅当，仅当 Fxq),(0时，称时，称x被被M接受。接受。 ),(|)(0*FxqxxML并且18NFA, -NFA等价 所有 NFA 都是-NFA. 仅仅不包含带的状态转换 要证明等价性，需证明对于任意的-NFA，能构建一个接收相同语言的NF

8、A 方法：把transition跟“真实”的状态转换结合起来19消除-Transition接受接受w后后aaa 跳转跳转状态q(q, wa) = -CLOSURE( ) P),(rarp1p2pnPa2022-3-22203.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)= ),(),(12aqaq2022-3-

9、22213.4 带空移动的有穷状态自动机带空移动的有穷状态自动机 与上图与上图-NFA等价的等价的NFA。 2022-3-22223.5 FA是正则语言的识别器是正则语言的识别器 3.5.1 FA与右线性文法与右线性文法 DFA M=(Q，q0，F)，处理句子，处理句子a1a2an的特性。的特性。 M按照句子按照句子a1a2an中字符的出现顺序，中字符的出现顺序，从开始状态从开始状态q0开始，依次处理字符开始，依次处理字符a1、a2、an，在这个处理过程中，每处理一，在这个处理过程中，每处理一的字符进入一个状态，最后停止在某个终的字符进入一个状态，最后停止在某个终止状态。止状态。 2022-3

10、-22233.5.1 FA与右线性文法与右线性文法 它每次处理且仅处理一个字符：第它每次处理且仅处理一个字符：第i步处理步处理输入字符输入字符ai。 对应于使用对应于使用(q，a)=p的状态转移函数的的状态转移函数的处理，相当于是在状态处理，相当于是在状态q完成对完成对a的处理，的处理，然后由然后由p接下去实现对后续字符的处理。接下去实现对后续字符的处理。 当当(q，a)=pF，且，且a是输入串的最后一是输入串的最后一个字符时，个字符时，M完成对此输入串的处理。完成对此输入串的处理。 2022-3-22243.5.1 FA与右线性文法与右线性文法A0 a1A1对应产生式对应产生式A0 a1A1

11、 a1a2A2对应产生式对应产生式A1 a2A2 a1a2an-1An-1对应产生式对应产生式An-2 an-1An-1 a1a2an-1an对应产生式对应产生式An-1 an2022-3-22253.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 2022-3-22263.5.1 FA与右线性文法与右线性文法 其中其中qn为为M的终止状态。考虑根据的

12、终止状态。考虑根据a1、a2、an，让，让A0与与q0对应、对应、A1与与q1对应、对应、A2与与q2对应、对应、An-2与与qn-2对应、对应、An-1与与qn-1对应。这样，就有希望得到满足定理对应。这样，就有希望得到满足定理2-4-1的正则文法的推导与的正则文法的推导与DFA的互相模拟的方的互相模拟的方式。式。 2022-3-22273.5.1 FA与右线性文法与右线性文法定理定理 3-3 FA接受的语言是正则语言。接受的语言是正则语言。证明：证明：(1) 构造。构造。基本思想是让基本思想是让RG的派生对应的派生对应DFA的移动。的移动。 设设DFA M=(Q，q0，F)，取右线性文法取

13、右线性文法 G=(Q，P，q0)， P=qap|(q，a)=pqa|(q，a)=pF2022-3-22283.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) 2022-3-22293.5.1 FA与右线性文法与右线性文法（3）关于关于句子。句子

14、。 如果如果q0 F，则，则 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)。定理得证。定理得证。 2022-3-22303.5.1 FA与右线性文法与右线性文法 例：例：与下图所给与下图所给DFA等价的正则文法等价的正则文法qs0|0q0|1q1q00|0q0|1q1q10q2|1|1q0q20q1|1q22022-3-22313.5.1 FA与右线性文法与右线性文法 例：

15、例：与下图所给的与下图所给的DFA等价的正则文法等价的正则文法 q00q1|1qt|2qtq10q1|1q2|2qtq20qt|1q2|2q3|2 q30qt|1qt|2q3|2qt 0qt|1qt|2qt 2022-3-22323.5.1 FA与右线性文法与右线性文法定理定理3-4 正则语言可以由正则语言可以由FA接受。接受。 证明：证明：（1）构造。）构造。基本思想：让基本思想：让FA模拟模拟RG的派生。的派生。设设G=(V，T，P，S)，且，且 L(G)，取取FA M=( VZ，T，S，Z)，Z V。2022-3-22333.5.1 FA与右线性文法与右线性文法 对对 (a，A)TV B

16、|AaBPZ如果如果AaP(A，a)= B|AaBP如果如果Aa P 用用B(A，a)与产生式与产生式AaB对应对应 用用Z(A，a)与产生式与产生式Aa对应。对应。2022-3-22343.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-1anP2022-3-22353.5.1 FA与右线性文法与右线性文法A1(S，a1)，A2(A1，a2)，An-

17、1(An-2，an-1)，Z(An-1，an) Z(S，a1a2an-1an ) a1a2an-1anL(M)对于对于 ，按照定理，按照定理2-5和定理和定理2-6处理。处理。2022-3-22363.5.1 FA与右线性文法与右线性文法 例例 3-10 构造与所给正则文法等价的构造与所给正则文法等价的FA： G1：E0A|1B A1|1C B0|0C C0B|1A 2022-3-22373.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)=

18、A对应对应C1A2022-3-22383.5.1 FA与右线性文法与右线性文法2022-3-22393.5.1 FA与右线性文法与右线性文法推论推论3-1 FA与正则文法等价。与正则文法等价。证明：根据定理证明：根据定理3-3和定理和定理3-4即可得到。即可得到。 2022-3-22403.5.1 FA与左线性文法与左线性文法 按照推导来说，句子按照推导来说，句子a1a2an-1an中的字符中的字符被推导出的先后顺序正好与它们在句子中被推导出的先后顺序正好与它们在句子中出现的顺序相反；而按照归约来看，它们出现的顺序相反；而按照归约来看，它们被归约成语法变量的顺序则正好与它们在被归约成语法变量的

19、顺序则正好与它们在句子中出现的顺序相同：句子中出现的顺序相同：a1，a2，an-1，an。可见，归约过程与。可见，归约过程与FA处理句子字符的处理句子字符的顺序是一致的，所以可考虑依照顺序是一致的，所以可考虑依照“归约归约”来研究来研究FA的构造。的构造。 2022-3-22413.5.1 FA与左线性文法与左线性文法 对于形如对于形如Aa的产生式：在推导中，一旦的产生式：在推导中，一旦使用了这样的产生式，句型就变成了句子，使用了这样的产生式，句型就变成了句子，而且而且a是该句子的第一个字符；按是该句子的第一个字符；按“归约归约”理解，对句子的第理解，对句子的第1个字符，根据形如个字符，根据形

20、如Aa的产生式进行归约。对应到的产生式进行归约。对应到FA中，中，FA从开从开始状态出发，读到句子的第一个字符始状态出发，读到句子的第一个字符a，应，应将它将它“归约归约”为为A。我们如果考虑用语法变。我们如果考虑用语法变量对应量对应FA的状态，那么，此时我们需要引的状态，那么，此时我们需要引入一个开始状态，比如说：入一个开始状态，比如说：Z。这样，对应。这样，对应形如形如Aa的产生式，可以定义的产生式，可以定义A(Z，a)。 2022-3-22423.5.1 FA与左线性文法与左线性文法 按照上面的分析，对应于形如按照上面的分析，对应于形如ABa的产生的产生式：式：FA应该在状态应该在状态B

21、读入读入a时，将状态转换时，将状态转换到到A。也可以理解为：在状态。也可以理解为：在状态B，FA已经将已经将当前句子的、处理过的前缀当前句子的、处理过的前缀“归约归约”成了成了B，在此时它读入在此时它读入a时，要将时，要将Ba归约成归约成A，因此，因此，它进入状态它进入状态A。 2022-3-22433.5.1 FA与左线性文法与左线性文法 按照按照“归约归约”的说法，如果一个句子是文的说法，如果一个句子是文法法G产生的语言的合法句子，它最终应该被产生的语言的合法句子，它最终应该被归约成文法归约成文法G的开始符号。所以，的开始符号。所以，G的开始的开始符号对应的状态就是相应的符号对应的状态就是

22、相应的FA的终止状态。的终止状态。 如何解决好开始符号只有一个，而如何解决好开始符号只有一个，而DFADFA的终的终止状态可以有多个的问题。止状态可以有多个的问题。 2022-3-22443.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)=C2022-3-22453.5.1 FA与左线性文法与左线性文法G2：EA0|B1A1|C1B0|C0CB0|A1 2022-3-22463.5.1 FA与左线性文法与左

23、线性文法 定理定理3-5 左线性文法与左线性文法与FA等价。等价。 2022-3-22473.6 FA的一些变形的一些变形 3.6.1 双向有穷状态自动机双向有穷状态自动机 确定的双向有穷状态自动机确定的双向有穷状态自动机(two-way deterministic finite automaton，2DFA)M=(Q，q0，F) Q、q0、F的意义同的意义同DFA。 2022-3-22483.6.1 双向有穷状态自动机双向有穷状态自动机 ：QQL，R，S，对，对 (q，a)Q 如果如果(q，a)= p，L，它表示，它表示M在状态在状态q读入读入字符字符a，将状态变成，将状态变成p，并将读头向

24、左移动一个，并将读头向左移动一个带方格而指向输入字符串的前一个字符。带方格而指向输入字符串的前一个字符。 如果如果(q，a)= p，R，它表示，它表示M在状态在状态q读入读入字符字符a，将状态变成，将状态变成p，并将读头向右移动一个，并将读头向右移动一个带方格而指向输入字符串中下一个字符。带方格而指向输入字符串中下一个字符。 如果如果(q，a)= p，S，它表示，它表示M在状态在状态q读入读入字符字符a，将状态变成，将状态变成p，读头保持在原位不动。，读头保持在原位不动。 2022-3-22493.6.1 双向有穷状态自动机双向有穷状态自动机 M接受的语言接受的语言 L(M)=x| q0 x*

25、xp且且pF 是是2DFA接受的接受的语言。语言。定理定理3-6 2DFA与与FA等价。等价。2022-3-22503.6.1 双向有穷状态自动机双向有穷状态自动机 不确定的双向有穷状态自动机不确定的双向有穷状态自动机(two-way nondeterministic finite automaton，2NFA)M=(Q，q0，F) Q、q0、F的意义同的意义同DFA。 ：Q2QL，R，S 。2022-3-22513.6.1 双向有穷状态自动机双向有穷状态自动机 (q，a)= ( p1，D1)( p2，D2) ，(pm,Dm) 表示表示M在状态在状态q读入字符读入字符a，可以选择地将，可以选择

26、地将状态变成状态变成p1同时按同时按D1实现对读头的移动、实现对读头的移动、或者将状态变成或者将状态变成p2同时按同时按D2实现对读头的实现对读头的移动、移动、或者将状态变成或者将状态变成pm同时按同时按Dm实实现对读头的移动。其中现对读头的移动。其中D1，D2，DmL，R，S，表示的意义与，表示的意义与2DFA2DFA的定的定义表示的意义相同义表示的意义相同。 2022-3-22523.6.1 双向有穷状态自动机双向有穷状态自动机定理定理3-7 2NFA与与FA等价。等价。 2022-3-22533.6.2 带输出的带输出的FA Moore机机 M=(Q，q0) Q、q0、的意义同的意义同D

27、FA。 输出字母表输出字母表(output alphabet)(output alphabet)。 ：Q为输出函数。对为输出函数。对 qQ，(q)=a表示表示M在状态在状态q时输出时输出a。 2022-3-22543.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) 2022-3-22553.6.2 带输出的带输出的FA Mealy机机 M=(Q，q0) 输出字母表。输出字母表。 ：Q为输出函数。对为输出函数。对

28、 (q，a)Q，(q，a)=d表示表示M在状态在状态q读读入字符入字符a时输出时输出d。2022-3-22563.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) 2022-3-22573.6.2 带输出的带输出的FA Moore机处理该串时每经过一个状态，就输机处理该

29、串时每经过一个状态，就输出一个字符：输出字符和状态一一对应；出一个字符：输出字符和状态一一对应； Mealy机处理该串时的每一个移动输出一个机处理该串时的每一个移动输出一个字符：输出字符和移动一一对应。字符：输出字符和移动一一对应。 2022-3-22583.6.2 带输出的带输出的FA 定理定理3-8 Moore机与机与Mealy机等价机等价。2022-3-22593.7 小结小结 本章讨论正则语言的识别器本章讨论正则语言的识别器FA。包括包括DFA、NFA、-NFA。RG与与FA的等的等价性。简单介绍带输出的价性。简单介绍带输出的FA和双向和双向FA。 FA M是一个五元组，是一个五元组，M=(Q，q0，F)，它可以用状态转移图表示。，它可以用状态转移图表示。 M接受