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

UJS5/19/2024 10:33 PM1第四章非确定性与NFA n n确定型计算确定型计算计算的每一步都按照唯一的方计算的每一步都按照唯一的方式跟在前一步的后面。当自动机处于给定的状式跟在前一步的后面。当自动机处于给定的状态读下一个输入符号时，机器的下一个状态是态读下一个输入符号时，机器的下一个状态是确定的。确定的。n n非确定型自动机中，在任何一点，下一个状态非确定型自动机中，在任何一点，下一个状态可能存在若干个选择。非确定型自动机是确定可能存在若干个选择。非确定型自动机是确定型自动机的推广，因此任何确定型自动机型自动机的推广，因此任何确定型自动机(DFA)(DFA)都是一台非确定型自动机都是一台非确定型自动机(NFA)(NFA)，此外，此外，非确定型自动机应该有一些另外的性质。非确定型自动机应该有一些另外的性质。8/3/2023 2:24 PMwww.kmitwan.co1UJS5/19/2024 10:33 PM2第四章非确定性与NFAn n4.1 非确定型有穷自动机4.1.1 NFA4.1.1 NFA引例引例4.1.2 NFA4.1.2 NFA的计算的计算4.1.3 NFA4.1.3 NFA的例子的例子n n4.2 NFA的形式定义4.2.1 NFA4.2.1 NFA的形式定义的形式定义4.2.2 NFA4.2.2 NFA计算的形式定义计算的形式定义8/3/2023 2:24 PMwww.kmitwan.co2UJS5/19/2024 10:33 PM3NFANFA与与DFADFA的区别：的区别：n nDFADFA的每一个状态恰好有一个转移箭头射出；而的每一个状态恰好有一个转移箭头射出；而NFANFA在同一状态对同一输入可能有在同一状态对同一输入可能有0 0个个,1,1个，甚至多个箭头个，甚至多个箭头射出。射出。n n譬如：譬如：N1N1中中q1q1状态下对状态下对1 1有有2 2个输出，而个输出，而q2q2状态对状态对1 1没有没有输出。输出。n nDFADFA的箭头标记符号都来自字母表；的箭头标记符号都来自字母表；NFANFA中允许空字中允许空字符符，甚至允许射出，甚至允许射出0 0个个,1,1个，或者多个箭头带个，或者多个箭头带 的箭头的箭头射出。射出。8/3/2023 2:24 PMwww.kmitwan.co3UJS5/19/2024 10:33 PM4第四章非确定性与NFAn n4.1 非确定型有穷自动机4.1.1 NFA4.1.1 NFA引例引例4.1.2 NFA4.1.2 NFA的计算的计算4.1.3 NFA4.1.3 NFA的例子的例子n n4.2 NFA的形式定义4.2.1 NFA4.2.1 NFA的形式定义的形式定义4.2.2 NFA4.2.2 NFA计算的形式定义计算的形式定义8/3/2023 2:24 PMwww.kmitwan.co4UJS5/19/2024 10:33 PM5三类看法：n n机器分裂论n n并行计算论n n可能性树”8/3/2023 2:24 PMwww.kmitwan.co5UJS5/19/2024 10:33 PM6n n机器分裂论机器分裂论 如：如：N1N1中，在中，在q1q1状态输入状态输入1 1时，机器把自己裂成两时，机器把自己裂成两个备份，并且每一个备份都并行地执行下去。个备份，并且每一个备份都并行地执行下去。N1N1中，在中，在q3q3状态输入状态输入0 0时，输入符号不在任何射出时，输入符号不在任何射出的箭头上，则找个机器备份及其关联的计算分支一的箭头上，则找个机器备份及其关联的计算分支一块死掉。块死掉。如果机器的某一个备份在输入的末端在接受状态，如果机器的某一个备份在输入的末端在接受状态，则这台则这台NFANFA接受输入串。接受输入串。接受输入串。接受输入串。如果遇到如果遇到，不用读任何输入，机器分裂成多个备份，不用读任何输入，机器分裂成多个备份，每一个标记每一个标记 的箭头有一个备份跟踪，还有一个停留的箭头有一个备份跟踪，还有一个停留在当前状态。在当前状态。8/3/2023 2:24 PMwww.kmitwan.co6UJS5/19/2024 10:33 PM7n n并行计算论并行计算论 非确定性可以看作若干过程能同时运行的一类并行非确定性可以看作若干过程能同时运行的一类并行计算。当计算。当NFANFA分头跟踪若干选择时，这对应于一个分头跟踪若干选择时，这对应于一个过程过程“分叉分叉”成若干子过程，各个子过程分别进行。成若干子过程，各个子过程分别进行。如果这些子过程中至少有一个接受，则整个计算接如果这些子过程中至少有一个接受，则整个计算接受。受。n n“可能性树可能性树”树根对应计算的开始，树中的每一个分支点对应计树根对应计算的开始，树中的每一个分支点对应计算中机器有多种选择的点。如果计算中至少有一个算中机器有多种选择的点。如果计算中至少有一个分支结束在接受状态，则机器接受。分支结束在接受状态，则机器接受。8/3/2023 2:24 PMwww.kmitwan.co7UJS5/19/2024 10:33 PM8n n例题例题1：对非确定型有穷状态自动机N1输入串010110。8/3/2023 2:24 PMwww.kmitwan.co8UJS5/19/2024 10:33 PM98/3/2023 2:24 PMwww.kmitwan.co9UJS5/19/2024 10:33 PM10n n手指记忆法：用手指按住状态图中的状态，表示当前所处的状态，并行多个状态用多个手指表示，上图中最多时同时需要用5个手指头。n n尝试用手指头记忆的方式来试验，确认一下N1是否接受含有101或11作为子串的所有字符串。8/3/2023 2:24 PMwww.kmitwan.co10UJS5/19/2024 10:33 PM11非确定型有穷状态自动机在以下几个方面是有用的：n n每一台NFA可以转换成一台等价DFA，n n构造NFA有时比直接构造DFA容易，n n一台NFA可能比等价的DFA小得多或功能更容易理解n n有穷自动机特别容易理解，有穷自动机的非确定性也是对能力更强的计算模型的非确定性的一个很好引入。8/3/2023 2:24 PMwww.kmitwan.co11UJS5/19/2024 10:33 PM12第四章非确定性与NFAn n4.1 非确定型有穷自动机4.1.1 NFA4.1.1 NFA引例引例4.1.2 NFA4.1.2 NFA的计算的计算4.1.3 NFA4.1.3 NFA的例子的例子n n4.2 NFA的形式定义4.2.1 NFA4.2.1 NFA的形式定义的形式定义4.2.2 NFA4.2.2 NFA计算的形式定义计算的形式定义8/3/2023 2:24 PMwww.kmitwan.co12UJS5/19/2024 10:33 PM13n n例题2：设A是0,1上倒数第3个符号为1的所有字符串组成的语言，设计识别A的自动机。8/3/2023 2:24 PMwww.kmitwan.co13UJS5/19/2024 10:33 PM148/3/2023 2:24 PMwww.kmitwan.co14UJS5/19/2024 10:33 PM15n n注意：注意：n n描述N2的最小的DFA，需要8个状态n n对应的DFA有助于我们理解N2n n思考题：下图是N2的一个修改，用树型图转化一下，看看它识别什么语言？构建的其对应的DFA？8/3/2023 2:24 PMwww.kmitwan.co15UJS5/19/2024 10:33 PM16n n例题例题3：考虑NFAN3，它的输入字母表0由一个符号组成。8/3/2023 2:24 PMwww.kmitwan.co16UJS5/19/2024 10:33 PM17n nN3表示所有形如0k的字符串，其中k是2或者3的倍数。可接受空串，00，000，但是不能接受0和00000。n n使用让该自动机最容易理解，当然，N3可以用DFA表示，不过理解上不够直观。8/3/2023 2:24 PMwww.kmitwan.co17UJS5/19/2024 10:33 PM18n n例题例题4：考虑NFAN4，它的输入字母表为a,b，考察N4所能识别的语言。N4能识别，a,baba和baa,而不接受b,bb,babba。思考，如何将这个NFA转化为DFA8/3/2023 2:24 PMwww.kmitwan.co18UJS5/19/2024 10:33 PM19第四章非确定性与NFAn n4.1 非确定型有穷自动机4.1.1 NFA4.1.1 NFA引例引例4.1.2 NFA4.1.2 NFA的计算的计算4.1.3 NFA4.1.3 NFA的例子的例子n n4.2 NFA的形式定义4.2.1 NFA4.2.1 NFA的形式定义的形式定义4.2.2 NFA4.2.2 NFA计算的形式定义计算的形式定义8/3/2023 2:24 PMwww.kmitwan.co19UJS5/19/2024 10:33 PM20FA和DFA很多地方类似，其本质的不同存在于转移函数。n nDFA中，转移函数取一个状态和一个输入符号，产生下一个状态。n nNFA中，转移函数取一个状态和一个输输入符号或空串入符号或空串，产生可能的下一个状态状态的集合的集合。8/3/2023 2:24 PMwww.kmitwan.co20UJS5/19/2024 10:33 PM21第四章非确定性与NFAn n4.1 非确定型有穷自动机4.1.1 NFA4.1.1 NFA引例引例4.1.2 NFA4.1.2 NFA的计算的计算4.1.3 NFA4.1.3 NFA的例子的例子n n4.2 NFA的形式定义4.2.1 NFA4.2.1 NFA的形式定义的形式定义4.2.2 NFA4.2.2 NFA计算的形式定义计算的形式定义8/3/2023 2:24 PMwww.kmitwan.co21UJS5/19/2024 10:33 PM22n n定义：非确定型有穷自动机定义：非确定型有穷自动机是一个5元组(Q,q0,F)，其中Q Q是一个有穷状态集；是一个有穷状态集；是一个有穷字母表；是一个有穷字母表；:Q Q P P(Q Q)是一个转移函数是一个转移函数q q0 0 Q Q是起始状态是起始状态F F属于属于Q Q是接受状态集。是接受状态集。说明：定义中=，P(Q)表示Q的幂集，是Q的所有子集组成的集合。8/3/2023 2:24 PMwww.kmitwan.co22UJS5/19/2024 10:33 PM23n n例题5：N1的形式化描述8/3/2023 2:24 PMwww.kmitwan.co23UJS5/19/2024 10:33 PM24n nN N1=(1=(Q Q,q q1,1,F F)Q Q=q q1,1,q q2,2,q q3,3,q q4 4；=0,1=0,1；如表所示如表所示 q q1 1 Q Q是起始状态是起始状态 F F=q q4 4。01q1 q1 q1,q2q2 q3 q3 q3 q4 q4 q4 q4 8/3/2023 2:24 PMwww.kmitwan.co24UJS5/19/2024 10:33 PM25第四章非确定性与NFAn n4.1 非确定型有穷自动机4.1.1 NFA4.1.1 NFA引例引例4.1.2 NFA4.1.2 NFA的计算的计算4.1.3 NFA4.1.3 NFA的例子的例子n n4.2 NFA的形式定义4.2.1 NFA4.2.1 NFA的形式定义的形式定义4.2.2 NFA4.2.2 NFA计算的形式定义计算的形式定义8/3/2023 2:24 PMwww.kmitwan.co25UJS5/19/2024 10:33 PM26n n定义定义2：设N=(Q,q0,F)是一台NFA，是字母表上的一个字符,如果把写成=y1y2ym，其中yi是的成员。如果存在Q中的状态序列r0，r1，r2，rm，满足下述条件：(1)(1)r0=qr0=q0 0(2)(2)ri+1ri+1 (ri ri,yi+1 yi+1),),i i=0,1,=0,1,m m-1-1(3)(3)r rn n F Fn n则N接受接受。8/3/2023 2:24 PMwww.kmitwan.co26UJS5/19/2024 10:33 PM27n说明：n n条件1说机器从起始状态开始n n条件2说状态ri+1 是处于状态ri读到yi+1时允许的下一个状态集合n n条件3表示最后一个状态是接受状态8/3/2023 2:24 PMwww.kmitwan.co27UJS5/19/2024 10:33 PM28Question&Answer8/3/2023 2:24 PMwww.kmitwan.co28