CM1025 计算机科学基础 第 8 周 DFA 示例
确定性有限自动机（DFA）设计详解
1. 语言定义与设计目标
语言L：所有以 a开头 且以 b结尾 的 {a, b} 字符串。
合法字符串：abb, ab, aabb
非法字符串：b, baa, abba
2. DFA设计步骤
(1) 初始状态 q₀
读a（合法开头）：转移到 q₂（检查后续字符）。
读b（非法开头）：转移到 q₁（陷阱状态，直接拒绝）。
(2) 陷阱状态 q₁（dummy state）
自循环：无论输入a或b，保持在q₁。
作用：一旦进入，后续所有字符均被拒绝。
(3) 中间状态 q₂
立即观看
0