形式语言与自动机理论--第三章 有限状态自动机-2（第七周）

1、第第3章章 有穷状态自动机有穷状态自动机 1.语言的识别语言的识别2.有穷状态自动机有穷状态自动机3.不确定的有穷状态自动机不确定的有穷状态自动机4.带空转移的有穷状态自动机带空转移的有穷状态自动机5.FA是正则语言的识别器是正则语言的识别器6.FA的一些变形的一些变形7.小结小结13.不确定的有穷状态自动机不确定的有穷状态自动机 确定的有穷状态自动机确定的有穷状态自动机DFA:在任一状态下给在任一状态下给定输入，下一个跳转状态是唯一的。定输入，下一个跳转状态是唯一的。 另一种构造自动机的可能：另一种构造自动机的可能：希望是接受希望是接受L=L=x|x0，1*，且，且x含有子串含有子串00或或

2、11的的FA：23.不确定的有穷状态自动机不确定的有穷状态自动机希望是接受希望是接受x|x0，1*，且，且x 的倒数第的倒数第10个字符为个字符为1的的FA如下如下 ：33.不确定的有穷状态自动机不确定的有穷状态自动机这两个图所给的这两个图所给的“FA”与前面我们所定义的与前面我们所定义的D DFA的区的区别在于：别在于： 并不是对于所有的并不是对于所有的(q，a)Q,(q，a)都有都有一个状态与它对应；一个状态与它对应； 并不是对于所有的并不是对于所有的(q，a)Q,(q，a)只对只对应一个状态。应一个状态。 “FA”在任意时刻可以处于有穷多个状态。在任意时刻可以处于有穷多个状态。 “FA”

3、具有具有“智能智能”。43.不确定的有穷状态自动机不确定的有穷状态自动机定义定义3-7：不确定的有穷状态自动机：不确定的有穷状态自动机(non-deterministic finite automaton ,NFA) M是一个五元组是一个五元组M=(Q，q0，F) Q、q0、F的意义同的意义同DFA。：Q2Q，对，对 (q，a)Q，(q，a)= p1，p2，pm表示表示M在状态在状态q读入字符读入字符a，可以选择地将状，可以选择地将状态变成态变成p1、或者、或者p2、或者、或者pm ，并将读头向右移动一，并将读头向右移动一个带方格而指向输入字符串的下一个字符。个带方格而指向输入字符串的下一个字

4、符。 53.不确定的有穷状态自动机不确定的有穷状态自动机FA的状态转移图、的状态转移图、FA的状态对应的等价类、的状态对应的等价类、FA的即时描的即时描述对述对NFA都有效。都有效。接受接受x|x0，1*，且，且x含有子串含有子串00或或11的的FA对应的移动对应的移动函数定义表。函数定义表。63.不确定的有穷状态自动机不确定的有穷状态自动机状态说明状态说明状态状态输入字符输入字符01启动状态启动状态q0q0，q1 q0，q2 q1q3 q2q3终止状态终止状态q3q3q373.不确定的有穷状态自动机不确定的有穷状态自动机接受接受x|x0，1*，且，且x 的倒数第的倒数第10个字符为个字符为1

5、的的FA对应的移动函数定义表。对应的移动函数定义表。83.不确定的有穷状态自动机不确定的有穷状态自动机状态说明状态说明状态状态输入字符输入字符01启动状态启动状态q0q0 q0，q1 q1q2q2 q2q3q3 q3q4q4 q4q5q5 q5q6q6 q6q7q7 q7q8q8 q8q9 q9 q9q10 q10终止状态终止状态q1093.不确定的有穷状态自动机不确定的有穷状态自动机将将扩充为扩充为QQ2:*对任意的对任意的qQ，w*，a，定义，定义 a)，(rp，使得w)，(q r|p),() 2(),() 1 (waqqq103.不确定的有穷状态自动机不确定的有穷状态自动机a)(q,a)

6、(q,p|pa)(r,p,|pa)(r,p),(q, r|p),(),(qraqaq和关于和关于DFADFA的结论一样，两值相同，也不的结论一样，两值相同，也不用区分这两个符号。用区分这两个符号。 113.不确定的有穷状态自动机不确定的有穷状态自动机进一步扩充进一步扩充的定义域：的定义域：2Q*2Q。对任意的。对任意的P Q，w*PqwqwP),(),(123.不确定的有穷状态自动机不确定的有穷状态自动机由于，对由于，对 (q，w)Q* ),(),(),(wqwqwqqq所以，不一定严格地区分所以，不一定严格地区分的第的第1个分量是一个个分量是一个状态还是一个含有一个元素的集合。状态还是一个含

7、有一个元素的集合。 133.不确定的有穷状态自动机不确定的有穷状态自动机对任意的对任意的qQ，w*，a： (q，wa)=(q，w)，a) 对输入字符串对输入字符串a1a2an (q，a1a2an)=(q, a1), a2)，)，an) 。143.不确定的有穷状态自动机不确定的有穷状态自动机定义定义3-8：M接受接受(识别识别)的语言的语言 设设M=(Q，q0，F) 是一个是一个NFA，对于对于 x*，如果如果(q0，x) F，则称，则称x被被M接受，如果接受，如果(q0，x)F=，则称，则称M不不接受接受x。L(M)=x| x*且且(q0，x) F，称为称为由由M接受接受(识别识别)的语言。的

8、语言。 153.不确定的有穷状态自动机不确定的有穷状态自动机对于一个输入字符，对于一个输入字符，NFA与与DFA的差异是前者可以的差异是前者可以进入若干个状态，而后者只能进入一个惟一的状态。进入若干个状态，而后者只能进入一个惟一的状态。虽然从虽然从DFA看待问题的角度来说，看待问题的角度来说，NFA在某一时刻在某一时刻同时进入若干个状态，但是，这若干个状态合在一同时进入若干个状态，但是，这若干个状态合在一起的起的“总效果总效果”相当于它处于这些状态对应的一个相当于它处于这些状态对应的一个“综合状态综合状态”。因此，我们考虑让因此，我们考虑让DFA用一个状态去对应用一个状态去对应NFA的一的一组

9、状态。组状态。 163.不确定的有穷状态自动机不确定的有穷状态自动机NFA M1=(Q，1，q0，F1)与与DFA M2=(Q2，2，q0，F2)的对应关系：的对应关系：NFA从开始状态从开始状态q0启动，我们就让相应的启动，我们就让相应的DFA从状态从状态q0启动。所以启动。所以q0= q0。 对于对于NFA 的一个状态组的一个状态组q1，q2，qn，如果，如果NFA在此状态组时读入字符在此状态组时读入字符a后可以进入状态组后可以进入状态组p1，p2，pm,则让相应的则让相应的DFA在状态在状态q1，q2，qn读入字符读入字符a时，进入状态时，进入状态p1，p2，pm。 173.不确定的有穷

10、状态自动机不确定的有穷状态自动机定理定理 3-1 NFA与与DFA等价。等价。证明：证明：只需证明对于任意给定的只需证明对于任意给定的NFA，存在与之等价的，存在与之等价的DFA。(1)(1)构造与构造与NFA M1等价的等价的DFA M2 。 M1=(Q，1，q0，F1) M2=(Q2，2，q0，F2) Q2=2Q F2=p1，p2，pm|p1，p2，pm Q&p1，p2，pmF1 183.不确定的有穷状态自动机不确定的有穷状态自动机2(q1，q2，qn，a)=p1，p2，pm1(q1，q2，qn，a)= p1，p2，pm (2) 证明证明1(q0，x)= p1，p2，pm 2(q0

11、，x)=p1，p2，pm。 设设x*，施归纳于，施归纳于|x| x=，1(q0，)= q0,2(q0，)=q0 193.不确定的有穷状态自动机不确定的有穷状态自动机设当设当|x|=n是结论成立。下面证明当是结论成立。下面证明当|x|=n+1是结论也成立。是结论也成立。不妨设不妨设x=wa，|w|=n，a 1 1(q(q0 0，wa)=wa)=1 1( (1 1(q(q0 0，w)w)，a)a) = =1 1(q(q1 1，q q2 2，q qn n ，a)a) =p=p1 1，p p2 2，p pm m 由归纳假设，由归纳假设， 1 1(q(q0 0，w)=qw)=q1 1，q q2 2，q

12、qn n 2 2(q(q0 0 ，w)=qw)=q1 1，q q2 2，q qn n 203.不确定的有穷状态自动机不确定的有穷状态自动机根据根据2的定义，的定义， 2(q1，q2，qn，a)=p1，p2，pm 1(q1，q2，qn，a)=p1，p2，pm 所以，所以，2(q0，wa)=2(2(q0，w)，a) =2(q1，q2，qn，a) =p1，p2，pm 213.不确定的有穷状态自动机不确定的有穷状态自动机 故，如果故，如果1(q0，wa)= p1，p2，pm则必有则必有2(q0，wa)= p1，p2，pm。由上述推导可知，反向的推导也成立。这就是说，由上述推导可知，反向的推导也成立。这

13、就是说，结论对结论对|x|=n+1也成立。也成立。 由归纳法原理，结论对由归纳法原理，结论对 x*成立。成立。 223.不确定的有穷状态自动机不确定的有穷状态自动机(3) 证明证明L(M1)=L(M2) 设设xL(M1)，且，且1(q0，x)= p1，p2，pm，从而从而1(q0，x)F1,这就是说，这就是说， p1，p2，pmF1，由由F2的定义，的定义，p1，p2，pmF2。233.不确定的有穷状态自动机不确定的有穷状态自动机再由再由(2)知，知，2(q0，x)=p1，p2，pm所以，所以，xL(M2)。故。故L(M1) L(M2)。 反过来推，可得反过来推，可得L(M2) L(M1)。从

14、而从而L(M1)=L(M2)得证。得证。 综上所述，定理成立。综上所述，定理成立。24例例 3-7 图图3-9所示的所示的NFA 对应的对应的DFA的状的状态转移函数如表态转移函数如表3-7所示。所示。 图图3-925表表3-7 状态转移函数状态转移函数状态说明状态说明状态状态输入字符输入字符01启动启动 q0q0,q1q0,q2 q1q3 q2q3终止终止 q3q3q3 q0,q1q0,q1,q3q0,q2 q0,q2q0,q1q0,q2,q3终止终止 q0,q3q0,q1,q3q0,q2,q3 q1,q2q3q3终止终止 q1,q3q3q3终止终止 q2,q3q3q3 q0,q1,q2q0

15、,q1,q3q0,q2,q3终止终止 q0,q1,q3q0,q1,q3q0,q2,q3终止终止 q0,q2,q3q0,q1,q3q0,q2,q3终止终止 q1,q2,q3q3q3终止终止 q0,q1,q2,q3q0,q1,q3q0,q2,q3 263.不确定的有穷状态自动机不确定的有穷状态自动机不可达状态不可达状态(inaccessible state)(inaccessible state)：不存在从不存在从qq0 0 对应的顶点出发，到达该状态对应的顶点的路。我对应的顶点出发，到达该状态对应的顶点的路。我们称此状态从开始状态是不可达的。们称此状态从开始状态是不可达的。表表3-7中，所有标记

16、中，所有标记“ ”的状态是从开始状态可达的状态是从开始状态可达的，其他是不可达的的，其他是不可达的无用的。无用的。 273.不确定的有穷状态自动机不确定的有穷状态自动机构造给定构造给定NFA等价的等价的DFA策略策略（1 1）先只把开始状态）先只把开始状态q0填入表的状态列中，计算填入表的状态列中，计算在在q0状态下各输入的输出；将得到的新状态填入状状态下各输入的输出；将得到的新状态填入状态列表中；态列表中；（2 2）如果状态列表有未处理的状态，则任选一个未）如果状态列表有未处理的状态，则任选一个未处理的状态处理的状态q1，q2，qn，对，对中的每个字符中的每个字符a，计算计算(q1，q2，q

17、n，a)，并填入相应的表项中，并填入相应的表项中（3 3）如果）如果(q1，q2，qn，a)在表的状态列未出在表的状态列未出现过，则将它填入表的状态列。现过，则将它填入表的状态列。（4 4）如此重复下去，直到表的状态列中不存在未处）如此重复下去，直到表的状态列中不存在未处理的状态。理的状态。 283.不确定的有穷状态自动机不确定的有穷状态自动机图图 3-11 图图3-9所示所示NFA的等价的等价DFA 294. 带空移动的有穷状态自动机带空移动的有穷状态自动机 接受语言接受语言0n1m2k|n，m，k0的的NFA 304. 带空移动的有穷状态自动机带空移动的有穷状态自动机 接受语言接受语言0n

18、1m2k|n，m，k0的的NFA是否可以构造成是否可以构造成下图所示的下图所示的“-NFA ”？ 其构造显然比图其构造显然比图1-13所示的所示的NFA更容易。更容易。当然还希望它们是等价的。当然还希望它们是等价的。314. 带空移动的有穷状态自动机带空移动的有穷状态自动机 定义定义3-9：带空移动的不确定的有穷状态自动机：带空移动的不确定的有穷状态自动机(non-deterministic finite automaton with -moves,-NFA)M=(Q，q0，F)，Q、q0、F的意义同的意义同DFA。 ：Q()2Q 324. 带空移动的有穷状态自动机带空移动的有穷状态自动机 非

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

20、动移动)，并且选择地将状态变，并且选择地将状态变成成p1、p2、或者或者pm。344. 带空移动的有穷状态自动机带空移动的有穷状态自动机 进一步扩充进一步扩充的定义域：的定义域：2Q*2Q。对任意的。对任意的P Q，w* 。对任意的对任意的qQ，w*，a。 -CLOSURE(q)=p|从从q到到p有一条标记为有一条标记为的路的路。定义为从定义为从 q 经所有的经所有的路径可以到达的状态（包括路径可以到达的状态（包括q自身）自身） PppCLOSUREPCLOSURE)()()2(354. 带空移动的有穷状态自动机带空移动的有穷状态自动机)(),() 3(qCLOSUREq),(),(),(),

21、(|)(),()4(wqrararpwqrpPPCLOSUREwaq使得36 4. 带空移动的有穷状态自动机带空移动的有穷状态自动机进一步扩展移动函数：进一步扩展移动函数：2 Q2Q 。 对任意对任意(P，a)2 Q。 PqaqaP),(),()5(PqwqwP),(),()6(374. 带空移动的有穷状态自动机带空移动的有穷状态自动机在在-NFA中，对任意中，对任意a，qQ，),(),(aqaq需要严格区分。需要严格区分。38图图3-14 所示所示-NFA状状态态 012012q0 q1 q0q0,q1,q2q0,q1,q2q1,q2q2q1 q2 q1q1,q2q1,q2q2q2 q2q2q2394. 带空移动的有穷状态自动机带空移动的有穷状态自动机定义定义3-10：M接受接受