软考——初识有限自动机

最近一直在忙软件设计师考试,由于没有参加自考,不像自考人员对于软考内容接受起来那么容易。其中第一个让自己头疼的就是FSM(有限状态自动机),视频中是针对题来讲的,而软考书中又都是一些专业术语、一些晦涩的数学式子。软考讲课小组中我又负责讲这部分内容,哎呀!通过查一些资料,理解好多了。

一、专业性的解释(百度百科)

有限状态自动机(FSM "finite state
machine" 或者FSA "finite state automaton" )是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态,每个状态可以迁移到零个或多个状态,输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。有限状态自动机是自动机理论的研究对象。

二、闲言碎语

参加自考的童鞋应该对FSM不陌生,因为编译原理中都学了。其实编译器就是用了FSM来做词法分析的。对于这一个初次接触的人,就没那么容易了。FSM的概念在网上一搜可以搜一大堆出来,但估计相当一部分人也看不大明白。

现实生活中,状态是随处可见的,并且通过不同的状态来做不同的事。比如冷了加衣服;饿了吃饭;困了睡觉等。这里的冷了、饿了、困了是三种不同的状态,并且根据这三个状态的转变驱动了不同行为的产生(加衣服、吃饭和睡觉)。

三、再看FSM是什么

所谓有限状态机,就是由有限个状态组成的机器。再看上面举到的例子:人就是一部机器,能感知三种状态(冷、饿、困)。由于气温降低所以人会觉得冷;由于到了吃饭的时间所以觉得饿;由于晚上12点所以觉得困。状态的产生以及改变都是由某种条件的成立而出现的。不考虑FSM的内部结构时,它就像是一个黑箱子,如下图:

左边是输入一系列条件,FSM通过判定,然后输出结果。

四、FSM的处理流程

上图FSM屏蔽了判定的过程,事实上FSM是由有限多个状态组成的,每个状态相当于FSM的一个部件。比如要判断一个整数是否偶数,其实只需要判断这个整数的最低位是否为0就行了,

对数字5来说,它的二进制表示为0101。二进制只能为0或1,所以二进制的字符集合为:{0, 1},对应到FSM来说,就是有2种状态,分别为S0和S1。如果用FSM来处理,它总是从左边读取(当然也可以把FSM反过来),也就是从0101最左边那位开始输入:首先输入左边第一位0,停留在S0状态,然后输入第二位1,转到S1状态,再输入第三位0,则又回到S0状态,最后输入是后一位1则又回到S1状态。如下图所示:

上图忽略了一个很重要的细节,就是0和1是怎么输入的。状态S0和状态S1是FSM里的2个小部件,它们分别关联了0和1(也可以说是特定的输入语句),所以只能通过FSM来输入。当FSM接收到0时,它就交给S0去处理,这时S0就变成当前状态,然后对S0输入1,S0则将它交给S1去处理,这时S1就变成当前状态。如此这般,FSM持有有限多个状态,它可以接收输入并执行状态转移(比如将最初的0交给S0去处理)。状态S0和状态S1也是如此。

但是为什么最开始FSM接收输入的0后会交给S0去处理呢?这是因为FSM的默认状态是S0。就像是有一台电视机,它总是有默认的频道的,您一打开电视机就可以看到影像,即使是满屏的雪花点。而且可以在按下电视机的开关前预先调整频道,之后也可以调整频道。

五、再举个例子

文章开头部分已经提及过,编译器中的词法分析就是能通过FSM完成的,那么怎么完成的?标识符就是词法分析的一项内容。C语言中对标识符的规定为由“_”或以字母开头的由“_”、字母和数字组成的字符串,该标识符的定义可以表示为下图中的内容:

图中上方的是正规表达式,式中的a代表字母符{A,…,Z,a…,z},d代表数字字符{0,1,…,9}。图中下方是对应的FSM。通过编译器中的此自动机就能完成对词法的分析。

目前自己只能理解表面上的这些内容,讲得也比较粗浅,请拍砖,多多指导!

软考——初识有限自动机,布布扣,bubuko.com

时间: 05-03

软考——初识有限自动机的相关文章

软考之 编译原理

看完书后做了一套真题,都是眼泪呀,经过对试题的分析,发现弱点是编译原理和组成原理部分;因为这两块本来就是薄弱地带,再加上看书之后没有认真地总结过,就开始了真题,难免在做题时遇到困难,下面针对编译原理做一下总结,从一张思维导图开始: 从导图中可以看出,程序语言的部分都不是难点,分类和基本成分都是平时接触的,唯一需要去理解的就是可能平时不太去关注的,低级语言.高级语言.编译程序.解释程序的特点. 把中重点放在语言处理程序的部分,其中分为三部分: 1.汇编程序 其中需要明白的就是指令语句,伪指令语句和

软考之路--计算机背后的故事

文法:1.法制:法规. 2.文章的作法. 3.语法.语言的结构方式.包括词的构成和变化﹐词组和句子的组织.文法即文章的书写法规,一般用来指以文字.词语.短句.句子的编排而组成的完整语句和文章的合理性组织.这个是我们小时候接触过的关于文法的概念,那个时候的文法总是会和主语,宾语,谓语等联系在一起. 二十年过去了,今天她再次出现在我面前,还是一样的眼神,藏在记忆深处的"文法"跟眼前的这个"她"有什么不一样呢?在计算机科学中,文法是编译原理的基础,是描述一门程序设计语言和

软考-程序设计语言基础(编译原理)

首先声明一下,本系列软考的文章是针对软件设计师(中级)的. 在软件设计师考试中,关于程序设计语言这一章节,前面的知识很基础,像一些控制结构和数据类型的知识我想大家都非常熟练就没有总结在图里. 本章节的重点内容在于编译原理,编译原理指的是编译器是将汇编或高级计算机语言翻译为二进制机器语言代码的计算机程序.内容主要包括文法.正规式.有限自动机.语法推导树. 好了,不多说,还是老规矩用图来介绍. 重点看一下编译原理,展开前三项看看. 文法,是描述语法结构的形式规则: 正规式是描述程序语言单词的表达式,

软考网络工程师复习备考策略

软考网络工程师,是软考中级科目考试里面较为简单的一门科目,并且对个人专业技术提升非常有帮助.大家可以免费学习一下,徐老师在51上的最新免费备考视频.1小时学会如何高效备战软考网络工程师视频课程有技术方面的问题都可随时在课后留言.

备战2017软考网络工程师终极解密学习

本套餐学习地址 http://edu.51cto.com/pack/view/id-967.html 本套餐可获得徐朋老师考前冲刺押题串讲[直播QQ群418431085]本套餐包括视频课和直播课两大部分,1.视频课包括软考网络工程师基础知识.案例分析解析和19套网工分类强化视频.2.直播课包括四次网工选择题.案例分析题重点.难点.易考点押题冲刺.购买本套餐,专项老师一对一答疑及独家资料赠送!祝大家考试顺利.

软考-我们又打了一场战役

<抱歉 今天没有写完.明天继续更新> 今天4点半,交上答题纸走出考场,十几个人一起等去北京南站的公交.这一次软考算是正式的结束了.近两个月的时间,比较系统的再学校了一下之前学过的东西,复习也有得失,今天做个总结.本来用grindstone统计着各部分准备之间呢,结果一不小心把所有的记录都删除了..考试结果没下来,没考过就算给自己留下的一个经验吧. 我们整体的计划是这个样子的 基本我也是跟着计划走的.9月1到9月30之间穿插着牛腩的学习,算是预热阶段. j2se的视频 虽然放进软考的复习里面但是

软考——计算机体系结构

软考进入倒计时的时间了,也是我们该要颗粒归仓的时候了. 还记得第一遍看软考书的时候,计算机体系结构这块知识那叫一个蒙啊,当时是硬生生的给吞下去的,不过还好,现在再看一遍书感觉亲切多了,因为熟悉了. 先看我的导图:    导图思路: 先从宏观入手,想到计算机体系结构,你能想到什么呢?当让是一些列组成计算机的东西,比如我们熟悉的CPU.键盘.鼠标.硬盘等等,这些事计算机的硬件,我们把他们分成四类:CPU.存储器.I/O设备和存储器:当然,有了这些硬件,计算机还是不能工作,让它跑起来当然少不了指令系统

备战软考(4) 软考下午题攻略

软考的全称是全国计算机技术与软件专业技术资格(水平)考试,而我们今天讨论的是其中的中级职称的一个科目----软件设计师.这个级别的考试主要分为两大块基础知识和应用技术,分别在考试当天的上午和下午进行测试. 对于基础知识这块,因为考查的知识面很广,也很细,个人而言无法找到一个行之有效的办法能让你迅速的提高上午题的成绩,因此就不在这里总结了,我们要做的就是看书,做题,再看书,再做题,然后接着看书,在看书与做题的反复中,一个一个的消灭自己的知识盲点和填补知识漏洞,这样慢慢的也许会有提升,但不要企图短时

拿什么应对你我的软考

话说软考也马上要开水一个月了,但是对于软考还不是很理解,今天就让我们来聊一聊那些年一起经历过的软考! 软考是全国计算机技术与软件专业技术资格(水平)考试(简称计算机与软件考试)是由国家人力资源和社会保障部与工业和信息化部组织领导的国家级考试,目的是科学.公正地对全国计算机与软件专业技术人员进行专业技术资格.职业资格认定和专业技术水平测试. 所以说软考是中国计算机界最高水平的考试!通过了考试下边这张图就可以用来描述你了! 那么在未来你就可以很坦然来做这些事情!看车,看房,看包包,还可以大胆的扶老奶