有限自动机是对状态图的形式化描述也就是说，有限自动机可以等价地表示为状态图，一个状态图也可以表示成等价的FA有限自动机（Finite Automata）即FA有限自动机分为：  确定有限自动机（Deterministic Finite Automata）  非确定有限自动机（Nondeterministic Finite Automata）

### 有限自动机的概念及分类 #### 什么是有限自动机？ 有限自动机（Finite State Automaton, FSA），也被称为有穷自动机，是一种用于建模计算系统的抽象机器。它的主要功能是对输入字符串进行处理，并决定该字符串是否属于某个特定的形式语言[^2]。 #### 有限自动机的分类 有限自动机可以根据其行为特征分为两种基本类型：确定性有限自动机（Deterministic Finite Automaton, DFA）和非确定性有限自动机（Non-deterministic Finite Automaton, NFA）。这两种类型的自动机在结构上存在显著差异，具体如下： --- #### 确定性有限自动机（DFA） DFA 是一种特殊的有限自动机，在任何给定状态下，对于每个可能的输入符号都只有一个明确的状态转移。这意味着： - 对于任意状态 \( q \in Q \) 和 输入字符 \( a \in \Sigma \)，转移函数 \( \delta(q, a) \) 的结果总是唯一的一个状态。 - 不允许空移动（ε-move）的存在。 因此，DFA 的识别过程是完全确定性的，不需要回溯操作即可完成整个字符串的匹配[^3]。 --- #### 非确定性有限自动机（NFA） 相比之下，NFA 则具有更大的灵活性。在一个 NFA 中： - 同一状态下可能存在多个针对相同输入符号的有效转移； - 支持 ε 移动，即可以在不消耗任何实际输入的情况下改变当前所处的状态； - 当面临多条可行路径时，如果至少有一条能够成功接受，则认为整体运行有效。 尽管如此，理论上已经证明每台 NFA 均可被转化为一台等价的功能相同的 DFA 来实现同样的模式匹配任务[^4]。 --- #### 主要区别总结 | 特性 | **DFA** | **NFA** | |---------------------|---------------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------| | 转移规则 | 单一固定 | 可能有多重选择 | | 是否支持 ε 迁移 | 否 | 是 | | 接受条件 | 如果最终停驻的位置位于接收态之中则视为接纳 | 存在一序列动作使得最后达到终态就算作认可 | | 复杂度 | 较高 | 更低 | 上述对比表明虽然两者表面上有很大不同之处，但从表达能力上看它们并无本质差别——任一由 NFA 所描述的语言总能找到相应形式下的 DFA 描述之；反之亦然。 --- #### 如何将 NFA 转换为 DFA? 为了把一个给定的 NFA 转化成与其功能相等效的 DFA ，常用的方法叫做“子集构造算法”。此方法的核心思想在于利用幂集来扩展原初节点集合，从而形成新的单一实体作为目标设备中的单个结点代表原来那些潜在可能性组合而成的整体情况[^1]。 以下是 Python 实现这一转化逻辑的小例子: ```python def nfa_to_dfa(nfa_states, nfa_transitions, start_state, accept_states): dfa_states = [] unprocessed_states = [{start_state}] while unprocessed_states: current_set = unprocessed_states.pop(0) if current_set not in dfa_states: dfa_states.append(current_set) transitions = {} for symbol in nfa_transitions[next(iter(current_set))]: reachable = set() for state in current_set: try: reachable.update(nfa_transitions[state][symbol]) except KeyError: pass if reachable and reachable not in dfa_states: unprocessed_states.append(reachable) transitions[symbol] = reachable # Store the transition information somewhere... return {"states":dfa_states} ``` 注意这只是一个简化版框架示意代码片段，完整版本还需要考虑更多细节比如如何标记终止状态等问题。 ---