有限状态自动机PPT课件.pptx

1、有限状有限状态自自动机机Automatona machine without feelings引言引言计算机很重要的一个任务就是理解用户的输入信息，并进行相应的处理输入信息的形式可能是多种多样的敲击键盘点击按钮动作手势有一种简单而有效的处理方法是有限状态自动机（finite state automaton）2概要概要这一章我们将介绍有关有限状态自动机的基本知识背景形式定义构造方式应用示例3有限状有限状态自自动机机计算机程序通常要处理一系列的符号，例如文档、网页中的字母或词语，甚至包括另一个计算机程序中的文本计算机科学家们常常使用一种称为有限状态自动机（FSA）的流程图来处理这些输入尽管这些流程

2、图非常简单，它们却能适用于许多问题，不仅能处理输入的文本信息，还能设计计算机界面和寻找图像规律4寻宝游宝游戏我们将通过一个游戏来学习有关有限状态自动机的概念和知识你既可以和几个伙伴一起来玩这个游戏（参见视频），也可以自己一个人来玩（使用卡片）5寻宝游宝游戏设想一下你现在处于只有岛屿的世界，海盗船来往于不同的岛屿之间幸运的是，海盗们都非常友善，而且乐于让旅行的人“搭便船”每个岛屿配备了两艘船A和B，你可以任选其一开始你的旅途每当你到达一个岛屿，你都能再选一艘船A或B，但不能同时选两个6寻宝游宝游戏比如，在下面的小地图中，如果你从海盗岛启程，搭乘船A，你将会抵达船难湾；如果你再次搭乘船A，你将会回

3、到海盗岛7寻宝游宝游戏现在我们换一张有7座岛屿的地图，你的目标是找到从海盗岛到金银岛的路线唯一的问题是，地图上并没有标出箭头，你需要自己去探索旅行的路线为了达成这个目标，你可以问每座岛上的A船或B船各驶向哪里后面我们将具体解释如何进行这个游戏，从而了解自动机的构造形式8岛屿地地图9寻宝游宝游戏请将以下形式的卡片对折，让没有目的地信息的一面向上，这样你只能在到达某个岛屿之后，才能“询问”岛屿的每艘船的目的地只需将卡片翻过来即可10寻宝游宝游戏首先请准备一张如前面所示的空白的藏宝图，选择A船或者B船从海盗岛启程在到达下一个岛屿前，在地图上画上箭头并做好标签，因为过一会儿你可能会又回到这个岛屿，这样

4、就能记起上一次你选择的路线，避免重复持续这个过程，相信你很快就会找到金银岛了，加油！11实践与思考践与思考你能找到通往金银岛的路线么？请标记好你在地图上发现的路线当你完成了整幅地图之后，能指出去金银岛的最短航线么？你能找到包含有回路（即循环访问某些岛屿一次以上的）并能最终抵达金银岛的航线么？12路路线藏宝藏宝图13有限状有限状态自自动机机经过这个游戏，我们对有限状态自动机已经有了初步的认识游戏中的每一次航行，都只取决于你当前所在的岛屿以及你所选择的船只岛屿即表示自动机的状态，船只即表示自动机的输入生活中的许多场景，也许你未曾留意，但实际上都是有限状态自动机的模式14生活中的自生活中的自动机机当

5、你去银行的自动提款机上取现金时，这台机器的计算机程序将指示你的操作在这个程序中，所有可能的用户操作都被保存成为有限状态自动机的形式你每按一个按钮，有限状态自动机便自动将你导向图中的另一座“岛屿”这些“岛屿”在计算机中有相应的提示，比如“提取100元现金”，“打印回条”或者“取出您的磁卡”15自自动机的表示机的表示计算机科学家们使用圆圈来表示每座岛屿，用箭头指示移动的方向，从而用有限状态自动机的形式画出寻宝地图16自自动机的表示机的表示在上图中，最终藏有宝藏的岛屿用双线圆圈表示，最开始出发的岛屿由没有标记的箭头指示（数字1）用自动机的术语来说，一个岛屿被称为一个状态（state），“金银岛”则被

6、称为终结状态（accept state）之所以称为状态是因为它说明了在有了之前的输入后（输入A或输入B），你进入了自动机过程中哪一个阶段的结果17自自动机的表示机的表示如果某个输入的序列（例如BBAB），能够从初始状态，经过状态转移之后，到达“终结状态”，则说明这一输入是“可接受的”（acceptable）在我们的例子中，“可接受”表示这是一条正确的寻宝路线（并不一定是最短最好的），在其他自动机的应用中，接受状态可能有更具体的含义，如检查输入是否构成有效的命令序列18有限状有限状态自自动机机至此，我们对于“有限状态自动机”这个听起来很复杂的名字，终于可以明确其意义了“有限”（finite）是指

7、在逻辑图中有有限数量的状态（如岛）“状态”（state）是游戏中岛屿的别称“自动机”（automaton）是指能遵循简单规则自主运行的机器，即根据当前状态和输入决定所转移的下一个状态的机制19实践与思考践与思考在表示自动机的图（a）中，下面哪些输入能被接受ABBABAAABBBAAAABABAAAABA的共同点么？20实践与践与思考（作思考（作业）在表示自动机的图（b）中，下面哪些输入能被接受ABBAABABAABBABABAABBA能描述出被图（b）接受的指令的共同点么？21实践与思考践与思考在表示自动机的图（c）中，下面哪些输入能被接受BBBBBBAABBAAAA能描述出被图（c）接受的指

8、令的共同点么？22自自动机的形式定机的形式定义23自自动机的形式定机的形式定义24自自动机的机的应用用一些使用FSA的计算机程序专门用于处理文本中的句子，它们既可以自己造句，也可以处理用于输入的句子25自自动机的机的应用用使用如上图所示的自动机，选择状态图上任意的路径并记录得到的单词，便可以构造合法的句子同样，这个自动机也可以用来由识别用户输入的句子，检查其是否符合特定的“模式”试着自己设计一个能造句的FSA，并让其他人使用你的FSA来造句26识别美元的自美元的自动机机27识别派生派生词的自的自动机机28进阶讨论非确定有限状非确定有限状态自自动机机我们前面介绍的，都属于确定型的有限状态自动机（

9、Deterministic Finite Automation,DFA）与之相对应的还有非确定型的有限状态自动机（Nondeterministic Finite Automata,NFA）这里是所说的“确定”，主要指的是状态转移函数，非确定意味着在某个状态的相同输入下可能会有不同的转移状态30非非确定有限状确定有限状态自自动机机从状态图模型的角度考虑，NFA可以认为是允许从一个状态引申出去的两个箭头拥有同一个标记31NFA的形式定的形式定义32非非确定有限状确定有限状态自自动机机在这种情况下，对于同一个输入序列，自动机可能会有多条不同的转移路径，此时只需有一条路径最终到达终结状态，即认为该输入

10、是可接受的由于这样的特性，非确定有限状态自动机具有更好的灵活性，往往能用较少的状态来表示相同的可接受输入集合同时，在许多问题当中，它的构造形式也更符合人的直观思维33非确定有限状非确定有限状态自自动机机但是，非确定机也就意味着状态转移不再是唯一的了，这使得我们在用计算机实现时遇到了困难（还记得算法的定义么？）幸运的是，我们可以通过一定的转换规则，将非确定自动机变化为确定型的有限状态自动机，这个过程称为自动机的确定化一般的，我们可以先构造非确定型的有限状态自动机，再将其确定化以满足需要34具有具有输出的出的有限有限自自动机机前面涉及的有限状态自动机，都是用于对字母表上的输入序列进行识别，返回“接

11、受”或者“拒绝”两种信息之一现实生活中还有一种有限状态自动机，对于不同的输入序列，除内部状态不断改变外，还不断向系统外部输出各种信号就像我们前面提到过的银行ATM系统，会在你不同的操作过程中返回相应的提示信息35具有具有输出的有限自出的有限自动机机具有输出的有限状态自动机，一般没有终结状态集，不存在“接受”或者“拒绝”输入序列的问题在读入输入串的过程中，自动机的状态不断改变，并且在每个状态上都有输出一般的有限状态自动机可以看作只有0、1两种输出的自动机：终结状态输出1，非终结状态输出036具有具有输出的有限自出的有限自动机机根据输出机制的不同，具有输出的有限自动机又可以分为摩尔（Moore）机

12、和米利（Mealy）机两种摩尔机的输出只与自动机当前所处的状态有关米利机的输出与自动机当前所处的状态以及面临的输入有关37摩摩尔机的形式定机的形式定义38米利机米利机的形式定的形式定义39自自动机与正机与正则表达式表达式正则表达式是在计算机当中很常见的一种表示方法，常常用于描述和匹配符合特定规则的字符串正则表达式的定义十分简单，通过字符表中的元字符，只使用连接、并集和闭包三种运算在许多著名的文本编辑器和集成环境当中，如vi、grep、Editplus等等，都提供了对正则表达式的支持40自自动机与正机与正则表达式表达式大家可能最为熟悉的文本处理器应当是MS Word，还记得当中的“?”以及“*”

13、的作用么？正则表达式与有限状态自动机是完全等价的，可以相互转换，有兴趣的同学请自学相关的知识，试试用正则表达式描述前面那三个自动机所表示的序列41参考参考资料料更多关于自动机的内容，例如怎样确定化NFA，正则表达式与自动机如何转化，可以参考以下的文献自动机理论、语言和计算导论形式语言与自动机理论编译原理42无无处不在的自不在的自动机机自动机对我们生活的影响力之大可能会超出你的想象，它的应用场景可以说是无处不在的BBS信息监测系统自动售货机图像压缩和图像增强网络入侵检测信息爆发度检测XML文本匹配43无无处不在的自不在的自动机机世界上最庞大的、无数人每天都会用到的自动机是什么？那就是我们使用的万维网每个网页就好比一座岛屿，页面上的链接就是行驶在岛屿之间的船只截止2009年，中国的网页数量已经超过了300亿，但网络仍然是个有限状态自动机Google这样的搜索引擎公司也正是基于这一点，依靠“爬虫”（crawling）在网页链接间的探索，为我们提供索引信息44谷歌的谷歌的PageRank算法算法ADBCFE15%probability of a random jumpWPageRank算法迭代算法迭代结果果Q&A