有限状态自动机

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2011/9/28,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2011/9/28,#,有限状态自动机,Automaton,a machine without feelings,引言,计算机很重要的一个任务就是理解用户的输入信息，并进行相应的处理,输入,信息的形式可能是多种多样的,敲击键盘,点击按钮,动作,手势,有一种简单而有效的处理方法是有限状态自动机（,finite state automaton,）,2,概要,这一章我们将介绍有关有限状态自动机的基本知识,背景,形式,定义,构造方式,应用,示例,3,有限状态自动机,计算机程序通常要处理一系列的符号，例如文档、网页中的字母或词语，甚至包括另一个计算机程序中的文本,计算机科学家们常常使用一种称为有限状态自动机（,FSA,）的流程图来处理这些输入,尽管这些流程图非常简单，它们却能适用于许多问题，不仅能处理输入的文本信息，还能设计计算机界面和寻找图像规律,4,寻宝游戏,我们将通过一个游戏来学习有关有限状态自动机的概念和知识,你既可以,和几个伙伴一起来玩这个游戏（参见视频），也可以自己一个人来玩（使用卡片）,准备好了么？,开始我们的金银岛冒险之旅吧,5,寻宝游戏,设想一下你现在处于只有岛屿的世界，海盗船来往于不同的岛屿之间,幸运,的是，海盗们都非常友善，而且乐于让旅行的人“搭便船”,每个岛屿配备了两艘船,A,和,B,，你可以任选其一开始你的旅途,每当,你到达一个岛屿，你都能再选一艘船,A,或,B,，但不能同时选两个,6,寻宝游戏,比如，在下面的小地图中，如果你从海盗岛启程，搭乘船,A,，你将会抵达船难湾；如果你再次搭乘船,A,，你将会回到海盗岛,7,寻宝游戏,现在我们换一张有,7,座岛屿的地图，你的目标是找到从海盗岛到金银岛的路线,唯一的问题是，地图上并没有标出箭头，你需要自己去探索旅行的路线,为了达成,这个目标，你可以问每座岛上的,A,船或,B,船各驶向哪里,后面我们将具体解释如何进行这个游戏，从而了解自动机的构造形式,8,岛屿地图,9,寻宝游戏,请将以下形式的卡片对折，让没有目的地信息的一面向上，这样你只能在到达某个岛屿之后，才能“询问”岛屿的每艘船的目的地,只需将卡片翻过来即可,10,寻宝游戏,首先请准备一张如前面所示的空白的藏宝图，选择,A,船或者,B,船从海盗岛启程,在,到达下一个岛屿前，在地图上画上箭头并做好标签，因为过一会儿你可能会又回到这个岛屿，这样就能记起上一次你选择的路线，避免重复,持续,这个过程，相信你很快就会找到金银岛了，加油！,11,实践与思考,你能找到通往金银岛的路线么？请标记好你在地图上发现的路线,当,你完成了整幅地图之后，能指出去金银岛的最短航线么？,你能,找到包含有回路（即循环访问某些岛屿一次以上的）并能最终抵达金银岛的航线么？,12,路线藏宝图,13,有限状态自动机,经过这个游戏，我们对有限状态自动机已经有了初步的认识,游戏,中的每一次航行，都只取决于你当前所在的岛屿以及你所选择的船只,岛屿即表示自动机的状态，船只即表示自动机的输入,生活,中的许多场景，也许你未曾留意，但实际上都是有限状态自动机的模式,14,生活中的自动机,当你去银行的自动提款机上取现金时，这台机器的计算机程序将指示你的操作,在这个程序,中，所有可能的用户操作都被保存成为有限状态自动机的形式,你每按一个,按钮，有限状态自动机便自动将你导向图中的另一座“岛屿”,这些“岛屿”在计算机中有相应的提示，比如“提取,100,元现金”，“打印回条”或者“取出您的磁卡”,15,自动机的表示,计算机科学家们使用圆圈来表示每座岛屿，用箭头指示移动的方向，从而用有限状态自动机的形式画出寻宝地图,16,自动机的表示,在上图中，最终藏有宝藏的岛屿用双线圆圈表示，最开始出发的岛屿由没有标记的箭头指示（数字,1,）,用自动机的术语来说，一个岛屿被称为一个状态（,state,），“金银岛”则被称为终结状态（,accept state,）,之所以称为状态是因为它说明了在有了之前的输入后（输入,A,或输入,B,），你进入了自动机过程中哪一个阶段的结果,17,自动机的表示,如果某个输入的序列（例如,BBAB,），能够从初始状态，经过状态转移之后，到达“终结状态”，则说明这一输入是“可接受的”（,acceptable,）,在我们的,例子中，“可接受”表示这是一条正确的寻宝路线（并不一定是最短最好的），在其他自动机的应用中，接受状态可能有更具体的含义，如检查输入是否构成有效的命令序列,18,有限状态自动机,至此，我们对于“有限状态自动机”这个听起来很复杂的名字，终于可以明确其意义了,“有限”（,finite,）是指在逻辑图中有有限数量的状态（如岛）,“状态”（,state,）是游戏中岛屿的别称,“自动机”（,automaton,）是指能遵循简单规则自主运行的机器，即根据当前状态和输入决定所转移的下一个状态的机制,19,实践与思考,在表示自动机的图（,a,）中，下面哪些输入能被接受,AB,BABAA,ABBBA,AAABABA,AAABA,的共同点么？,20,实践与,思考（作业）,在,表示自动机的图,（,b,）,中，下面哪些输入能被接受,AB,BA,ABAB,AABB,ABABA,ABBA,能描述出被图,（,b,）,接受的指令的共同点么？,21,实践与思考,在,表示自动机的图,（,c,）,中，下面哪些输入能被接受,B,BBB,BBA,ABBA,AAA,能描述出被图,（,c,）,接受的指令的共同点么？,22,自动机的形式定义,23,自动机的形式定义,你能把这些自动机,表示成五元组的形式么,24,自动机的应用,一些使用,FSA,的计算机程序专门用于处理文本中的句子，它们既可以自己造句，也可以处理用于输入的句子,25,自动机的应用,使用如上图所示的自动机，选择状态图上任意的路径并记录得到的单词，便可以构造合法的句子,同样，这个自动机也可以用来由识别用户输入的句子，检查其是否符合特定的“模式”,试,着自己设计一个能造句的,FSA,，并让其他人使用你的,FSA,来造句,26,识别美元的自动机,27,识别派生词的自动机,28,进阶讨论,非确定有限状态自动机,我们前面介绍的，都属于确定型的有限状态自动机（,Deterministic Finite,Automation,DFA,）,与之,相对应的还有非确定型的有限状态自动机（,Nondeterministic Finite Automata,NFA,）,这里是所说的“确定”，主要指的是状态转移函数，非确定意味着在某个状态的相同输入下可能会有不同的转移状态,30,非,确定有限状态自动机,从状态图模型的角度考虑，,NFA,可以认为是允许从一个状态引申出去的两个箭头拥有同一个标记,31,NFA,的形式定义,32,非,确定有限状态,自动机,在这种情况下，对于同一个输入序列，自动机可能会有多条不同的转移路径，此时只需有一条路径最终到达终结状态，即认为该输入是可接受的,由于这样的特性，,非确定有限状态,自动机具有更好的灵活性，往往能用较少的状态来表示相同的可接受输入集合,同时，在许多问题当中，它的构造形式也更符合人的直观思维,33,非确定有限状态自动机,但是，非确定机也就意味着状态转移不再是唯一的了，这使得我们在用计算机实现时遇到了困难（还记得算法的定义么？）,幸运,的是，我们可以通过一定的转换规则，将非确定自动机变化为确定型的,有限,状态自动机，这个过程称为自动机的确定化,一般,的，我们可以先构造非确定型的,有限,状态自动机，再将其确定化以满足需要,34,具有输出的,有限,自动机,前面涉及的有限状态自动机，都是用于对字母表上的输入序列进行识别，返回“接受”或者“拒绝”两种信息之一,现实生活中还有一种有限状态自动机，对于不同的,输入序列，,除内部状态不断改变外，还不断向系统外部输出各种,信号,就像,我们前面提到过的银行,ATM,系统，会在你不同的操作过程中返回相应的提示信息,35,具有输出的有限自动机,具有输出的有限状态自动机，一般没有终结状态集，不存在“接受”或者“拒绝”输入序列的问题,在读入输入串的过程中,，,自动,机,的状态不断改变,，并且,在每个状态上都有,输出,一般的有限状态自动机可以看作只有,0,、,1,两种输出的自动机：终结状态输出,1,，非终结状态输出,0,36,具有输出的有限自动机,根据输出机制的不同，,具有输出的,有限自动机又可以分为摩尔（,Moore,）机和米利（,Mealy,）机两种,摩尔,机的输出只与自动机当前所处的状态有关,米利机的输出与自动机当前所处的状态以及面临的输入有关,37,摩尔机的形式定义,38,米利机,的形式定义,39,自动机与正则表达式,正则表达式是在计算机当中很常见的一种表示方法，常常用于描述和匹配符合特定规则的字符串,正则表达式的定义十分简单，通过字符表中的元字符，只使用连接、并集和闭包三种运算,在,许多著名的文本编辑,器和集成环境当中,，如,vi,、,grep,、,Editplus,等等，都提供了对正则表达式的支持,40,自动机与正则表达式,大家可能最为熟悉的文本处理器应当是,MS Word,，还记得当中,的“,?,”以及“,*,”的作用么？,它们就是正则表达式！,正则表达式与有限状态自动机是完全等价的，可以相互转换，有兴趣的同学请自学相关的知识，试试用正则表达式描述前面那三个自动机所表示的序列,41,参考资料,更多关于自动机的内容，例如怎样确定化,NFA,，正则表达式与自动机如何转化，可以参考以下的文献,自动机理论、语言和计算导论,形式语言与自动机理论,编译原理,42,无处不在的自动机,自动机对我们生活的影响力之大可能会超出你的想象，它的应用场景可以说是无处不在的,BBS,信息监测,系统,自动,售货机,图像压缩和,图像增强,网络入侵,检测,信息爆发度检测,XML,文本匹配,43,无处不在的自动机,世界上最庞大的、无数人每天都会用到的自动机是什么？那就是我们使用的万维网,每个网页就好比一座岛屿，页面上的链接就是行驶在岛屿之间的船只,截止,2009,年，中国的网页数量已经超过了,300,亿，但网络仍然是个有限状态自动机,Google,这样的搜索引擎公司也正是基于这一点，依靠“爬虫”（,crawling,）在网页链接间的探索，为我们提供索引信息,44,谷歌的,PageRank,算法,A,D,B,C,F,E,15%probability of a random jump,W,PageRank,算法迭代结果,Thank you,Q&A,