《形式语言与自动机理论--第三章 有限状态自动机-3（第八周）》由会员分享，可在线阅读，更多相关《形式语言与自动机理论--第三章 有限状态自动机-3（第八周）（43页珍藏版）》请在金锄头文库上搜索。
1、第第3章章 有穷状态自动机有穷状态自动机 1.语言的识别语言的识别2.有穷状态自动机有穷状态自动机3.不确定的有穷状态自动机不确定的有穷状态自动机4.带空转移的有穷状态自动机带空转移的有穷状态自动机5.FA是正则语言的识别器是正则语言的识别器6.FA的一些变形的一些变形7.小结小结15. FA是正则语言的识别器是正则语言的识别器对于任意正于任意正则语言言L，都有一个，都有一个满足定理足定理2-1的正的正则文法文法G=（V,T,P,S），使得），使得L=L（G）。）。由于由于G是右是右线性的，除了空性的，除了空产生式外，每个生式外，每个产生式生式的右部有且的右部有且仅有一个有一个终极符号。极符号
2、。L中任意句子中任意句子a1a2an在推在推导时有如下特征：有如下特征：从从G的开始符号的开始符号S开始，除了开始，除了a1a2an外外，每个每个句型中有且句型中有且仅有一个有一个语法法变量，而且此量，而且此语法法变量量总是句型的尾字符，因此，句型中的是句型的尾字符，因此，句型中的终极符号是依据极符号是依据它被推它被推导出来的先后出来的先后顺序序a1a2an依次排列的。依次排列的。25. FA是正则语言的识别器是正则语言的识别器 G的每步推的每步推导产生且生且仅能能产生生一个终极符号：第一个终极符号：第i步产生终极符号步产生终极符号ai。 使用形如使用形如AaB的产生式的推导，相当于是变的产生
3、式的推导，相当于是变量量A产生出产生出aB，而，而B负责后续字符的产生。负责后续字符的产生。 使用形如使用形如Aa的产生式的推导，相当于是变量的产生式的推导，相当于是变量A产生产生a后，整个推导就结束了。后，整个推导就结束了。35. FA是正则语言的识别器是正则语言的识别器 A0 a1A1 对应产生式对应产生式A0 a1A1 a1a2A2对应产生式对应产生式A1 a2A2 a1a2an-1An-1对应产生式对应产生式An-2 an-1An-1 a1a2an-1an对应产生式对应产生式An-1 an45. FA是正则语言的识别器是正则语言的识别器如果存在一个如果存在一个DFA M=(Q，q0，F
4、)，处理，处理句子句子a1a2an的特性。的特性。 M按照句子按照句子a1a2an中字符的出现顺序，从开始中字符的出现顺序，从开始状态状态q0开始，依次处理字符开始，依次处理字符a1、a2、an，在这，在这个处理过程中，每处理一的字符进入一个状态，最个处理过程中，每处理一的字符进入一个状态，最后停止在某个终止状态。后停止在某个终止状态。 55. FA是正则语言的识别器是正则语言的识别器 它它每每次次处处理理且且仅仅处处理理一一个个字字符符：第第i步步处处理理输输入入字字符符ai。 对对应应于于使使用用(q，a)=p的的状状态态转转移移函函数数的的处处理理，相相当当于于是是在在状状态态q完完成成
5、对对a的的处处理理，然然后后由由p接接下下去去实现对后续字符的处理。实现对后续字符的处理。 当当(q，a)=pF，且，且a是输入串的最后一个字符是输入串的最后一个字符时，时，M完成对此输入串的处理。完成对此输入串的处理。 65. 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 75. FA是正则语言的识别器是正则语言的识别器其中其中qn为为M的终止
6、状态。考虑根据的终止状态。考虑根据a1、a2、an，让，让A0与与q0对应、对应、A1与与q1对应、对应、A2与与q2对应、对应、An-2与与qn-2对应、对应、An-1与与qn-1对应。这样，就有希望对应。这样，就有希望得到满足定理得到满足定理2-4-1的正则文法的推导与的正则文法的推导与DFA的互相的互相模拟的方式。模拟的方式。 85. FA是正则语言的识别器是正则语言的识别器定理定理 3-3 FA接受的语言是正则语言。接受的语言是正则语言。证明：证明：(1) 构造。构造。基本思想是让基本思想是让RG的派生对应的派生对应DFA的移动。的移动。 设设DFA M=(Q，q0，F)，取右线性文法
7、取右线性文法 G=(Q，P，q0)， P=qap|(q，a)=pqa|(q，a)=pF95. 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) 105. FA是正则语言的识别器是正则语言的识别器（3）关于关于句子。句子。 如果如果q0 F，则，
8、则 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)。定理得证。定理得证。 115. FA是正则语言的识别器是正则语言的识别器例例 3-9 与图与图3-8 所给所给DFA等价的正则文法等价的正则文法qs0|0q0|1q1q00|0q0|1q1q10q2|1|1q0q20q1|1q2125. FA是正则语言的识别器是正则语言的识别器与图与图3-7 所给的所给的DFA等价的等价的正则文
9、法正则文法 q00q1|1qt|2qtq10q1|1q2|2qtq20qt|1q2|2q3|2 q30qt|1qt|2q3|2qt 0qt|1qt|2qt 13去掉陷阱状态去掉陷阱状态q00q1q10q1|1q2q21q2|2q3|2 q32q3|2 5. FA是正则语言的识别器是正则语言的识别器定理定理3-4 正则语言可以由正则语言可以由FA接受。接受。 证明：证明：（1）构造。）构造。基本思想：让基本思想：让FA模拟模拟RG的派生。的派生。设设G=(V，T，P，S)，且，且 L(G)，取取FA M=( VZ，T，S，Z)，Z V。145. FA是正则语言的识别器是正则语言的识别器对对 (a
10、，A)TV B|AaBPZ如果如果AaP(A，a)= B|AaBP如果如果Aa P 用用B(A，a)与产生式与产生式AaB对应对应 用用Z(A，a)与产生式与产生式Aa对应。对应。155. 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-1anP165. FA是正则语言的识别器是正则语言的识别器A1(S，a1)，A2(A1，a2)，An-1(An-
11、2，an-1)，Z(An-1，an) Z(S，a1a2an-1an ) a1a2an-1anL(M)对于对于 ，按照定理，按照定理2-5和定理和定理2-6处理。处理。175. FA是正则语言的识别器是正则语言的识别器例例 3-10 构造与所给正则文法等价的构造与所给正则文法等价的FA： G1：E0A|1B A1|1C B0|0C C0B|1A 185. 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对应对应C1A195. FA是正则
12、语言的识别器是正则语言的识别器205. FA是正则语言的识别器是正则语言的识别器推论推论3-1 FA与正则文法等价。与正则文法等价。证明：根据定理证明：根据定理3-3和定理和定理3-4即可得到。即可得到。 215. FA是正则语言的识别器是正则语言的识别器FA与左线性文法与左线性文法对于左线性文法来说，按照推导来说，句子对于左线性文法来说，按照推导来说，句子a1a2an-1an中的字符被推导出的先后顺序正好与它中的字符被推导出的先后顺序正好与它们在句子中出现的顺序相反；而按照归约来看，它们在句子中出现的顺序相反；而按照归约来看，它们被归约成语法变量的顺序则正好与它们在句子中们被归约成语法变量的
13、顺序则正好与它们在句子中出现的顺序相同：出现的顺序相同：a1，a2，an-1，an。可见，归约过程与可见，归约过程与FA处理句子字符的顺序是一致处理句子字符的顺序是一致的，所以可考虑依照的，所以可考虑依照“归约归约”来研究来研究FA的构造。的构造。 225. FA是正则语言的识别器是正则语言的识别器对于形如对于形如Aa的产生式：在推导中，一旦使用了的产生式：在推导中，一旦使用了这样的产生式，句型就变成了句子，而且这样的产生式，句型就变成了句子，而且a是该句是该句子的第一个字符；按子的第一个字符；按“归约归约”理解，对句子的第理解，对句子的第1个字符，根据形如个字符，根据形如Aa的产生式进行归约
14、。的产生式进行归约。对应到对应到FA中，中，FA从开始状态出发，读到句子的第从开始状态出发，读到句子的第一个字符一个字符a，应将它，应将它“归约归约”为为A。我们如果考虑。我们如果考虑用语法变量对应用语法变量对应FA的状态，那么，此时我们需要的状态，那么，此时我们需要引入一个开始状态，比如说：引入一个开始状态，比如说：Z。这样，对应形如这样，对应形如Aa的产生式，可以定义的产生式，可以定义A(Z，a)。 235. FA是正则语言的识别器是正则语言的识别器按照上面的分析，对应于形如按照上面的分析，对应于形如ABa的产生式：的产生式：FA应该在状态应该在状态B读入读入a时，将状态转换到时，将状态转
15、换到A。也可以。也可以理解为：在状态理解为：在状态B，FA已经将当前句子的、处理过已经将当前句子的、处理过的前缀的前缀“归约归约”成了成了B，在此时它读入，在此时它读入a时，要将时，要将Ba归约成归约成A，因此，它进入状态，因此，它进入状态A。 按照按照“归约归约”的说法，如果一个句子是文法的说法，如果一个句子是文法G产生产生的语言的合法句子，它最终应该被归约成文法的语言的合法句子，它最终应该被归约成文法G的的开始符号。所以，开始符号。所以，G的开始符号对应的状态就是相的开始符号对应的状态就是相应的应的FA的终止状态。的终止状态。245. FA是正则语言的识别器是正则语言的识别器例如：对文法例
16、如：对文法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)=C255. FA是正则语言的识别器是正则语言的识别器G2：EA0|B1A1|C1B0|C0CB0|A1 265. FA是正则语言的识别器是正则语言的识别器构造与给定的构造与给定的DFA等价的左线性文法：等价的左线性文法：DFA (的状态转移图的状态转移图)作如下作如下“预处理预处理”： 删除删除DFA的陷阱状态的陷阱状态(包括与之相关的弧包括与之相关的弧)； 在图中加一个识别状态在图中加一个识别状态z； “复复
17、制制”一一条条原原来来到到达达终终止止状状态态的的弧弧，使使它它从从原原来的起点出发，到达新添加的识别状态。来的起点出发，到达新添加的识别状态。 (4)如果启动状态是终止状态，则增加产生式如果启动状态是终止状态，则增加产生式z275. FA是正则语言的识别器是正则语言的识别器左线性文法构造依照以下两条进行左线性文法构造依照以下两条进行 如果如果(A，a)=B，则有产生式，则有产生式BAa； 如果如果(A，a)=B，且，且A是开始状态，则有产生式是开始状态，则有产生式Ba。 定理定理3-5 左线性文法与左线性文法与FA等价。等价。 285. FA是正则语言的识别器是正则语言的识别器构造与上面构造
18、与上面FA等价的左线性文法等价的左线性文法6. FA的一些变形的一些变形 6.1 双向有穷状态自动机双向有穷状态自动机 定义定义3-11：确定的双向有穷状态自动机：确定的双向有穷状态自动机(two-way deterministic finite automaton，2DFA)M=(Q，q0，F) Q、q0、F的意义同的意义同DFA。 306.1 双向有穷状态自动机双向有穷状态自动机：QQL，R，S，对，对 (q，a)Q 如果如果(q，a)= p，L，它表示，它表示M在状态在状态q读入字符读入字符a，将，将状态变成状态变成p，并将读头向左移动一个带方格而指向输入字，并将读头向左移动一个带方格而
19、指向输入字符串的前一个字符。符串的前一个字符。 如果如果(q，a)= p，R，它表示，它表示M在状态在状态q读入字符读入字符a，将，将状态变成状态变成p，并将读头向右移动一个带方格而指向输入字，并将读头向右移动一个带方格而指向输入字符串中下一个字符。符串中下一个字符。 如果如果(q，a)= p，S，它表示，它表示M在状态在状态q读入字符读入字符a，将，将状态变成状态变成p，读头保持在原位不动。，读头保持在原位不动。 316.1 双向有穷状态自动机双向有穷状态自动机定义定义3-12：M接受的语言接受的语言 L(M)=x| q0x*xp且且pF 是是2DFA接受的语言。接受的语言。定理定理3-6
20、2DFA与与FA等价。等价。326.1 双向有穷状态自动机双向有穷状态自动机定义定义3-13：不确定的双向有穷状态自动机：不确定的双向有穷状态自动机(two-way nondeterministic finite automaton，2NFA)M=(Q，q0，F) Q、q0、F的意义同的意义同DFA。 ：Q2QL，R，S 。336.1 双向有穷状态自动机双向有穷状态自动机(q，a)= ( p1，D1)( p2，D2) ，(pm,Dm) 表示表示M在状态在状态q读入字符读入字符a，可以选择地将状态变成，可以选择地将状态变成p1同时同时按按D1实现对读头的移动、或者将状态变成实现对读头的移动、或者
21、将状态变成p2同时按同时按D2实现对读头的移动、实现对读头的移动、或者将状态变成或者将状态变成pm同时同时按按Dm实现对读头的移动。其中实现对读头的移动。其中D1，D2，DmL，R，S，表示的意义与，表示的意义与2DFA2DFA的定义表示的意义的定义表示的意义相同相同。定理定理3-7 2NFA与与FA等价。等价。 346.2 带输出的带输出的FA 定义定义3-14：Moore机机 ，六元组：，六元组：M=(Q，q0) Q、q0、的意义同的意义同DFA。 输出字母表输出字母表(output alphabet)(output alphabet)。 ：Q为输出函数。对为输出函数。对 qQ，(q)=a
22、表示表示M在状态在状态q时输出时输出a。 356.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) (qn) 是一个长度为是一个长度为n+1的串的串366.2 带输出的带输出的FA 定义定义3-15：Mealy机机 ，六元组，六元组M=(Q，q0) 输出字母表。输出字母表。 ：Q为输出函数。对为输出函数。对 (q，a)Q，(q，a)=d表示表示M在状态在状态q读入字符读入字符a时输出时输出d。376.2 带输出的带输
23、出的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) 是一个长度为是一个长度为n的串的串386.2 带输出的带输出的FA Moore机机处处理理该该串串时时每每经经过过一一个个状状态态，就就输输出出一一个个字符：输出字符和状态一一对应；字符：输出字符和状态一一对应；Mealy机处理该串时的每一
24、个移动输出一个字符：机处理该串时的每一个移动输出一个字符：输出字符和移动一一对应。输出字符和移动一一对应。 396.2 带输出的带输出的FA 定义定义3-163-16：设：设Moore机机M1=(Q1，1，1，q01)Mealy机机M2=(Q2，2，2，q02)对对于于 x*，当当T1(x)=1(q0)T2(x)成成立立，则则它它们们是是等等价价的的其中，其中， T1(x)和和T2(x)分别表示分别表示M1和和M2关于关于x的输出。的输出。 定理定理3-8 Moore机与机与Mealy机等价机等价。407. 小结小结 本章讨论正则语言的识别器本章讨论正则语言的识别器FA。包括。包括DFA、NF
25、A、-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。417. 小结小结 NFA允许允许M在一个状态下读入一个字符时选择地进入在一个状态下读入一个字符时选择地进入某一个状态，对于某一个状态
26、，对于 x*，如果，如果(q0，x) F，则，则称称x被被M接受，如果接受，如果(q0，x)F=，则称，则称M不接受不接受x。M接受的语言接受的语言L(M)=x| x*且且(q0，x) F。 -NFA是是在在NFA的的基基础础上上，允允许许直直接接根根据据当当前前状状态态变变换换到到新新的的状状态态而而不不考考虑虑输输入入带带上上的的符符号号。对对 qQ，(q，)= p1，p2，pm表表示示M在在状状态态q不不读读入入任任何何字字符符，可可以以选选择择地地将将状状态态变变成成p1、p2、或或者者pm。这这叫叫做做M在在状态状态q做一个空移动。做一个空移动。 NFA与与DFA等价，等价，-NFA
27、与与NFA等价，统称它们为等价，统称它们为FA。 427. 小结小结 根根据据需需要要，可可以以在在FA中中设设置置一一种种特特殊殊的的状状态态陷陷阱状态。但是，不可达状态却是应该无条件地删除的。阱状态。但是，不可达状态却是应该无条件地删除的。 FA是是正正则则语语言言的的识识别别模模型型。分分别别按按照照对对推推导导和和归归约约的模拟，可以证明的模拟，可以证明FA和左线性文法、右线性文法等价。和左线性文法、右线性文法等价。 2DFA是是FA的的又又一一种种变变形形，它它不不仅仅允允许许读读头头向向前前移移动动，还还允允许许读读头头向向后后移移动动。通通过过这这种种扩扩充充，2DFA仍仍然然与与FA等价。等价。 Moore机机和和Mealy机机是是两两种种等等价价的的带带输输出出的的FA，Moore机机根根据据状状态态决决定定输输出出字字符符，Mealy机机根根据据移移动动决决定输出字符。定输出字符。 43
