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、掌握有限自动机与正规式的对应关系。