有限自动机

[yangsirgo]

定义

有线离散系统的抽象数学模型。 英文缩写 FSM 或者 FSA （FSM "finite state machine" 或者FSA "finite state automaton" ）

参见文章：https://blog.csdn.net/zhanglianhai555/article/details/24887081

例子

编译器中词法分析就是通过FSM完成的，如何完成的？

• 标识符是词法分析的一项内容。
• 正规C语言对标识符的规定是由“_”或者字母，数字组成的字符串。

例子1

解析：

• 在有限自助机的状态装换图中，每一个节点代表一个状态，其中双圈是终态节点。
• 从初态0出发，识别一个符号a后进入状态1，在状态1可识别出任意个a或者任意个b，再识别一个a而到达终态2。
• 答案是 B B

例子2

• 答案是 A
• 对于字符串“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”。

[yangsirgo]

例题2图片备注错误。入度为零不是啥都可以写。

[yangsirgo]

不确定有限自动机（NFA）状态转换图： 详细图片：

解析：例题是不确定的有限自动机，中间内容有多种可能（符号ε 代表不确定），但是从图中可以看出，从初态0开始，首字符只能为0，到终态结束之前，尾字符也只能为0，根据选项可以排除，所以选择A。