形式语言与自动机-4-非确定性与NFA课件

9/7/20239:46AM1第四章非确定性与NFA确定型计算——计算的每一步都按照唯一的方式跟在前一步的后面。当自动机处于给定的状态读下一个输入符号时，机器的下一个状态是确定的。非确定型自动机中，在任何一点，下一个状态可能存在若干个选择。非确定型自动机是确定型自动机的推广，因此任何确定型自动机(DFA)都是一台非确定型自动机(NFA)，此外，非确定型自动机应该有一些另外的性质。8/3/20232:24PMwww.kmitwan.co19/7/20239:46AM2第四章非确定性与NFA4.1非确定型有穷自动机4.1.1NFA引例4.1.2NFA的计算 4.1.3NFA的例子4.2NFA的形式定义 4.2.1NFA的形式定义 4.2.2NFA计算的形式定义8/3/20232:24PMwww.kmitwan.co29/7/20239:46AM3NFA与DFA的区别：DFA的每一个状态恰好有一个转移箭头射出；而NFA在同一状态对同一输入可能有0个,1个，甚至多个箭头射出。譬如：N1中q1状态下对1有2个输出，而q2状态对1没有输出。DFA的箭头标记符号都来自字母表；NFA中允许空字符ε，甚至允许射出0个,1个，或者多个箭头带ε的箭头射出。8/3/20232:24PMwww.kmitwan.co39/7/20239:46AM4第四章非确定性与NFA4.1非确定型有穷自动机4.1.1NFA引例4.1.2NFA的计算 4.1.3NFA的例子4.2NFA的形式定义 4.2.1NFA的形式定义 4.2.2NFA计算的形式定义8/3/20232:24PMwww.kmitwan.co49/7/20239:46AM5三类看法：机器分裂论并行计算论可能性树”8/3/20232:24PMwww.kmitwan.co59/7/20239:46AM6机器分裂论如：N1中，在q1状态输入1时，机器把自己裂成两个备份，并且每一个备份都并行地执行下去。N1中，在q3状态输入0时，输入符号不在任何射出的箭头上，则找个机器备份及其关联的计算分支一块死掉。如果机器的某一个备份在输入的末端在接受状态，则这台NFA接受输入串。如果遇到ε，不用读任何输入，机器分裂成多个备份，每一个标记ε的箭头有一个备份跟踪，还有一个停留在当前状态。8/3/20232:24PMwww.kmitwan.co69/7/20239:46AM7并行计算论非确定性可以看作若干过程能同时运行的一类并行计算。当NFA分头跟踪若干选择时，这对应于一个过程“分叉”成若干子过程，各个子过程分别进行。如果这些子过程中至少有一个接受，则整个计算接受。“可能性树”树根对应计算的开始，树中的每一个分支点对应计算中机器有多种选择的点。如果计算中至少有一个分支结束在接受状态，则机器接受。8/3/20232:24PMwww.kmitwan.co79/7/20239:46AM8例题1：对非确定型有穷状态自动机N1输入串010110。8/3/20232:24PMwww.kmitwan.co89/7/20239:46AM98/3/20232:24PMwww.kmitwan.co99/7/20239:46AM10手指记忆法：用手指按住状态图中的状态，表示当前所处的状态，并行多个状态用多个手指表示，上图中最多时同时需要用5个手指头。尝试用手指头记忆的方式来试验，确认一下N1是否接受含有101或11作为子串的所有字符串。8/3/20232:24PMwww.kmitwan.co109/7/20239:46AM11非确定型有穷状态自动机在以下几个方面是有用的：每一台NFA可以转换成一台等价DFA，构造NFA有时比直接构造DFA容易，一台NFA可能比等价的DFA小得多或功能更容易理解有穷自动机特别容易理解，有穷自动机的非确定性也是对能力更强的计算模型的非确定性的一个很好引入。8/3/20232:24PMwww.kmitwan.co119/7/20239:46AM12第四章非确定性与NFA4.1非确定型有穷自动机4.1.1NFA引例4.1.2NFA的计算

4.1.3NFA的例子4.2NFA的形式定义 4.2.1NFA的形式定义 4.2.2NFA计算的形式定义8/3/20232:24PMwww.kmitwan.co129/7/20239:46AM13例题2：设A是{0,1}上倒数第3个符号为1的所有字符串组成的语言，设计识别A的自动机。8/3/20232:24PMwww.kmitwan.co139/7/20239:46AM148/3/20232:24PMwww.kmitwan.co149/7/20239:46AM15注意：描述N2的最小的DFA，需要8个状态对应的DFA有助于我们理解N2思考题：下图是N2的一个修改，用树型图转化一下，看看它识别什么语言？构建的其对应的DFA？8/3/20232:24PMwww.kmitwan.co159/7/20239:46AM16例题3：考虑NFA—N3，它的输入字母表{0}由一个符号组成。8/3/20232:24PMwww.kmitwan.co169/7/20239:46AM17N3表示所有形如0k的字符串，其中k是2或者3的倍数。可接受空串，00，000，但是不能接受0和00000。使用ε让该自动机最容易理解，当然，N3可以用DFA表示，不过理解上不够直观。8/3/20232:24PMwww.kmitwan.co179/7/20239:46AM18例题4：考虑NFA—N4，它的输入字母表为{a,b}，考察N4所能识别的语言。N4能识别ε，a,baba和baa,而不接受b,bb,babba。思考，如何将这个NFA转化为DFA8/3/20232:24PMwww.kmitwan.co189/7/20239:46AM19第四章非确定性与NFA4.1非确定型有穷自动机4.1.1NFA引例4.1.2NFA的计算 4.1.3NFA的例子4.2NFA的形式定义

4.2.1NFA的形式定义 4.2.2NFA计算的形式定义8/3/20232:24PMwww.kmitwan.co199/7/20239:46AM20FA和DFA很多地方类似，其本质的不同存在于转移函数。DFA中，转移函数取一个状态和一个输入符号，产生下一个状态。NFA中，转移函数取一个状态和一个输入符号或空串，产生可能的下一个状态的集合。8/3/20232:24PMwww.kmitwan.co209/7/20239:46AM21第四章非确定性与NFA4.1非确定型有穷自动机4.1.1NFA引例4.1.2NFA的计算 4.1.3NFA的例子4.2NFA的形式定义

4.2.1NFA的形式定义

4.2.2NFA计算的形式定义8/3/20232:24PMwww.kmitwan.co219/7/20239:46AM22定义：非确定型有穷自动机是一个5元组(Q,∑,δ,q0,F)，其中Q是一个有穷状态集；∑是一个有穷字母表；δ:Q×∑ε→P(Q)是一个转移函数q0

∈Q是起始状态F属于Q是接受状态集。说明：定义中∑ε

=∑∪{ε}，P(Q)表示Q的幂集，是Q的所有子集组成的集合。8/3/20232:24PMwww.kmitwan.co229/7/20239:46AM23例题5：N1的形式化描述8/3/20232:24PMwww.kmitwan.co239/7/20239:46AM24N1=(Q,∑,δ,q1,F)Q={q1,q2,q3,q4}；∑={0,1}；δ如表所示q1

∈Q是起始状态F={q4}。01εq1

{q1}{q1,q2}Φq2{q3}Φ{q3}q3Φ{q4}Φq4{q4}{q4}Φ8/3/20232:24PMwww.kmitwan.co249/7/20239:46AM25第四章非确定性与NFA4.1非确定型有穷自动机4.1.1NFA引例4.1.2NFA的计算 4.1.3NFA的例子4.2NFA的形式定义 4.2.1NFA的形式定义

4.2.2NFA计算的形式定义8/3/20232:24PMwww.kmitwan.co259/7/20239:46AM26定义2：设N=(Q,∑,δ,q0,F)是一台NFA，ω是字母表∑上的一个字符,如果把ω写成ω=y1y2…ym，其中yi是∑ε的成员。如果存在Q中的状态序列r0，r1，r2，…，rm，满足下述条件：(1)r0=q0(2)ri+1∈δ(ri,yi+1),i=0,1,…,m-1(3)rn∈F则N接受ω。8/3/20232:24PMwww.k