CM1025 计算机科学基础 第七周 识别语言
有限自动机设计实例解析
1. 接受所有二进制字符串的自动机
目标语言：Σ = {0, 1}，接受所有可能的二进制字符串（包括空串 ε）。
设计方法：
单状态简化设计：
状态 A（既是初始状态也是接受状态）。
自循环转移：读 0 或 1 均保持在 A。
逻辑：任何输入均被接受，无需拒绝路径。
图示：
text
复制
下载
[A] ——0→ [A]
[A] ——1→ [A]
2. 接受以0结尾的二进制字符串的自动机
目标语言：所有以 0 结尾的字符串（如 0, 10, 1100）。
设计步骤：
状态定
立即观看
0