DFA（确定有限自动机）和NFA（不确定有限自动机）是形式语言与自动机理论中的核心概念，用于识别正则语言。DFA的转换函数具有确定性，即每个状态在给定输入字符下只能转移到唯一一个状态，其定义为 $ f: S \times \Sigma \to S $。而NFA允许从一个状态在某个输入字符下转移到多个状态，转换函数为 $ f: S \times \Sigma \to 2^S $，甚至可以包含ε\varepsilonε-转移（空串转移），这使得NFA在结构上更具灵活性。
尽管NFA表现出“不确定性”，但每一个NFA都可以通过子集构造法（Subset Construction）转换为等价的DFA，因此两者在语言识别能力上是等价的，均能识别且仅能识别正则语言。在实际应用中，如编译器的词法分析阶段，通常先由正则表达式构建NFA，再转化为DFA以提高匹配效率。
# 示例：简单DFA模拟器（识别以 'ab' 结尾的字符串）defdfa_accepts(input_string):state='s0'transition={('s0','a'):'s1',('s0','b'):'s0',('s1','a'):'s1',('s1','b'):'s2',('s2','a'):'s1',('s2','b'):'s0'}forcharininput_string:if(state,char)intransition:state=transition[(state,char)]else:returnFalse# 无定义转移，拒绝returnstate=='s2'# s2 是终态print(dfa_accepts("ab"))# Trueprint(dfa_accepts("aab"))# Trueprint(dfa_accepts("abb"))# False**确定有限自动机（DFA）和不确定有限自动机（NFA）**的计算机理论知识内容，属于程序设计语言基础中的形式语言与自动机部分，核心信息整理如下：
1. DFA的核心定义
DFA是一个五元组 ( M = (S, \Sigma, f, S_0, Z) )，其中：
- ( S ) 是状态集合，( \Sigma ) 是输入字符集，( f ) 是转换函数，( S_0 ) 是初态，( Z ) 是终态集合。
- 转换函数 ( f(A,a)=Q ) 表示：当前状态为 ( A )、输入字符为 ( a ) 时，转移到状态 ( Q )。
2. DFA的表示方式
- 状态转换图：以节点表示状态，有向弧表示转换（弧上标记输入字符），双圈节点表示终态。
- 状态转换矩阵：二维数组，行表示当前状态，列表示输入字符，元素表示转移后的状态。
3. 示例解析（图2-7）
以DFA ( M1 = ({s_0,s_1,s_2,s_3}, {a,b}, f, s_0, {s_3}) ) 为例：
- 转换图（图2-7a）：初态 ( s_0 )，终态 ( s_3 )，弧对应 ( f ) 的转换规则（如 ( s_0 ) 输入 ( a ) 到 ( s_1 )）。
- 转换矩阵（图2-7b）：行是状态，列是 ( a/b )，元素是转移后的状态（如 ( M[s_0,a]=s_1 )）。
4. DFA的语言识别
- 若存在从初态到终态的路径，路径上的字符连接成字符串 ( \omega )，则 ( \omega ) 可被DFA识别。
- DFA识别的语言 ( L(M) = {\omega \mid \omega ) 是初态到终态路径的字符序列}。
5. NFA的特点
NFA是不确定的有限自动机，与DFA的区别：
- 转换函数 ( f ) 是 ( S \times \Sigma \to 2^S )（返回状态集合，即一个状态输入字符后可转移到多个状态）。
- 有向弧的标记可以是空串 ( \varepsilon )。
补充背景
DFA/NFA是形式语言与自动机理论的基础模型，用于描述正则语言（可被正则表达式表示的语言），是编译原理中词法分析器的理论基础。
)
