2021下半年软件设计师考点分析：有限自动机

作者:匿名更新于： 2021-09-07 11:37:36

　　很多考生在备考2021下半年软件设计师考试，今天课课家小编为大家整理了软考中级软件设计师考点分析：有限自动机，供大家备考复习。

　　【考法分析】

　　本知识点的主要考查形式有：给出一个确定或不确定的有限自动机，指出其能够识别的字符串，或指出对应的正规式表示。

　　【要点分析】

　　1、定义：M=(S,∑, δ,S0,Z)

　　1)S是一个有限集，每个元素为一个状态

　　2)∑是一个有穷字母表，每个元素为一个输入字符

　　3)δ是转换函数：是一个单值对照

　　4)S0,属于S，是其唯一的初态

　　5)Z是一个终态集(可空)

　　2、一个有限自动机所识别的语言是从开始状态到终止状态所有路径上的字符串的集合。要判断一个字符串能否被指定的自动机识别，就看在该自动机的状态图中能否找到一条从开始状态到达终止状态的路径，且路径上的字符串等于需要识别的字符串。而对于其正规式，可以通过能够识别的字符串去总结规律。

　　例：下图所示的有限自动机中，s0是初始状态，s3为终止状态，该自动机不能识别()。

　　A.abab B.aaaa C.babb C.abba

　　问题解析：

　　一个有限自动机所识别的语言是从开始状态到终止状态所有路径上的字符串的集合。要判断一个字符串能否被指定的自动机识别，就看在该自动机的状态图中能否找到一条从开始状态到达终止状态的路径，且路径上的字符串等于需要识别的字符串。

　　对于字符串“abab”，其识别路径为s0→s1→s2→s1→s2，字符串结束时的状态不是终止状态，所以该自动机不能识别“abab”。

　　对于字符串“aaaa”，其识别路径为s0→s1→s3→s3→s3，字符串结束时的状态是终止状态，所以该自动机可以识别“aaaa”。

　　对于字符串“babb”，其识别路径为s0→s2→s1→s2→s3，字符串结束时的状态是终止状态，所以该自动机可以识别“babb”。

　　对于字符串“abba”，其识别路径为s0→s1→s2→s3→s3，字符串结束时的状态是终止状态，所以该自动机可以识别“abba”。

　　【备考点拨】

　　1、掌握有限自动机相关的基本概念;

　　2、掌握有限自动机能够识别的字符串判断;

　　3、掌握有限自动机与正规式的对应关系。

      课课家教育专注软考培训10年以上，一直坚持自主研发，将丰富的软考培训经验有效融入教程研发过程，自成体系的软考视频教程、软考培训教材和软考在线题库，使考生的学习更具系统性，辅导更具针对性。想要报考2021年软考的考生现在就可以开始备考了，报名课课家软考各科目考试赠送：辅导教材、历年真题、考前冲剌资料、在线模拟测试题库、老师专属答疑指导等，以保障学员顺利通过考试。

　　>>>>>>点击进入软考报名专题