形式语言与自动机-4-非确定性与NFA课件.ppt
《形式语言与自动机-4-非确定性与NFA课件.ppt》由会员分享,可在线阅读,更多相关《形式语言与自动机-4-非确定性与NFA课件.ppt(28页珍藏版)》请在三一办公上搜索。
1、3/21/2023 12:28 AM,1,第四章非确定性与NFA,确定型计算计算的每一步都按照唯一的方式跟在前一步的后面。当自动机处于给定的状态读下一个输入符号时,机器的下一个状态是确定的。非确定型自动机中,在任何一点,下一个状态可能存在若干个选择。非确定型自动机是确定型自动机的推广,因此任何确定型自动机(DFA)都是一台非确定型自动机(NFA),此外,非确定型自动机应该有一些另外的性质。,3/21/2023 12:28 AM,2,第四章非确定性与NFA,4.1 非确定型有穷自动机4.1.1 NFA引例4.1.2 NFA的计算4.1.3 NFA的例子4.2 NFA的形式定义4.2.1 NFA的
2、形式定义4.2.2 NFA计算的形式定义,3/21/2023 12:28 AM,3,NFA与DFA的区别:DFA的每一个状态恰好有一个转移箭头射出;而NFA在同一状态对同一输入可能有0个,1个,甚至多个箭头射出。譬如:N1中q1状态下对1有2个输出,而q2状态对1没有输出。DFA的箭头标记符号都来自字母表;NFA中允许空字符,甚至允许射出0个,1个,或者多个箭头带的箭头射出。,3/21/2023 12:28 AM,4,第四章非确定性与NFA,4.1 非确定型有穷自动机4.1.1 NFA引例4.1.2 NFA的计算4.1.3 NFA的例子4.2 NFA的形式定义4.2.1 NFA的形式定义4.2
3、.2 NFA计算的形式定义,3/21/2023 12:28 AM,5,三类看法:机器分裂论并行计算论可能性树”,3/21/2023 12:28 AM,6,机器分裂论如:N1中,在q1状态输入1时,机器把自己裂成两个备份,并且每一个备份都并行地执行下去。N1中,在q3状态输入0时,输入符号不在任何射出的箭头上,则找个机器备份及其关联的计算分支一块死掉。如果机器的某一个备份在输入的末端在接受状态,则这台NFA接受输入串。如果遇到,不用读任何输入,机器分裂成多个备份,每一个标记的箭头有一个备份跟踪,还有一个停留在当前状态。,3/21/2023 12:28 AM,7,并行计算论非确定性可以看作若干过程
4、能同时运行的一类并行计算。当NFA分头跟踪若干选择时,这对应于一个过程“分叉”成若干子过程,各个子过程分别进行。如果这些子过程中至少有一个接受,则整个计算接受。“可能性树”树根对应计算的开始,树中的每一个分支点对应计算中机器有多种选择的点。如果计算中至少有一个分支结束在接受状态,则机器接受。,3/21/2023 12:28 AM,8,例题1:对非确定型有穷状态自动机N1输入串010110。,3/21/2023 12:28 AM,9,3/21/2023 12:28 AM,10,手指记忆法:用手指按住状态图中的状态,表示当前所处的状态,并行多个状态用多个手指表示,上图中最多时同时需要用5个手指头。
5、尝试用手指头记忆的方式来试验,确认一下N1是否接受含有101或11作为子串的所有字符串。,3/21/2023 12:28 AM,11,非确定型有穷状态自动机在以下几个方面是有用的:,每一台NFA可以转换成一台等价DFA,构造NFA有时比直接构造DFA容易,一台NFA可能比等价的DFA小得多或功能更容易理解有穷自动机特别容易理解,有穷自动机的非确定性也是对能力更强的计算模型的非确定性的一个很好引入。,3/21/2023 12:28 AM,12,第四章非确定性与NFA,4.1 非确定型有穷自动机4.1.1 NFA引例4.1.2 NFA的计算4.1.3 NFA的例子4.2 NFA的形式定义4.2.1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言 自动机 确定性 NFA 课件
链接地址:https://www.31ppt.com/p-3765003.html