CM1025 计算机科学基础 第 8 周 确定性有限自动机（DFA）与非确定性有限自动机（NFA）
深入理解有限自动机的确定性与非确定性
1. 问题引入：两种异常情况分析
在分析输入 1100 和 11001 时，我们发现自动机可能面临两种问题：
转移不足（如状态B缺少对 0 的转移，导致 1100 无法处理）。
转移冲突（如状态B对 0 有多个转移，导致 11001 选择路径时不确定）。
这引出了自动机的核心分类：确定性有限自动机（DFA） 和 非确定性有限自动机（NFA）。
2. 确定性有限自动机（DFA）
定义：
每个状态对每个输入符号 有且仅有一条转移路径。
唯一初始状态，无歧义启动。
示例修正
立即观看
0