有穷自动机（Finite Automaton，简称 FA）

有穷自动机是一种数学模型，用于描述一个系统的状态转换过程。它在计算机科学中广泛应用，尤其是在正则表达式、编译器、语言识别、控制系统等领域。有限自动机由一组状态、输入符号、状态转移规则、初始状态和终止状态组成。

有穷自动机的组成部分：

1. 状态集合 (Q)：有限自动机的所有可能状态的集合。
2. 输入字母表 (Σ)：输入符号的有限集合，表示自动机能够接收的字符或符号。
3. 转移函数 (δ)：描述状态之间如何转移的规则，通常是一个映射，定义了当前状态和输入符号对应的下一个状态。
4. 初始状态 (q₀)：自动机开始执行时的初始状态。
5. 接受状态 (F)：如果自动机在处理完所有输入后处于这些状态中的任何一个，那么自动机就会接受输入（即输入字符串是有效的）。

有穷自动机的分类：

1. 确定性有穷自动机 (DFA，Deterministic Finite Automaton)：

   • 在给定的每个状态和输入符号对下，自动机只能转移到一个唯一的下一个状态。
   • 每个状态和输入符号都有一个明确的状态转移，不允许有多个转移路径。
   • 特点：确定性、每个状态只会有一个转移规则。

   DFA 的特点：

   • 无回溯。
   • 每个状态对于每个输入符号都有唯一的转移。

2. 非确定性有穷自动机 (NFA，Nondeterministic Finite Automaton)：

   • 在给定的状态和输入符号对下，自动机可以有多个可能的下一状态，或者没有任何转移。
   • NFA 允许有多个转移路径或空转移（即不消耗输入符号的转移）。
   • 特点：非确定性、同一状态和输入符号可能有多个转移路径。

   NFA 的特点：

   • 可以有多个可能的状态转移路径。
   • 可能有空转移（ε转移）。

DFA 与 NFA 的关系：

• 等价性：虽然 DFA 和 NFA 的工作方式不同，但它们具有等价性。任何一个 NFA 都可以转换成等价的 DFA，反之亦然。虽然从理论上讲，NFA 在状态转换上更灵活，但它的计算能力和 DFA 是一样的。
• 效率差异：DFA 转换为 NFA 后，可能会产生更多的状态，因此 NFA 更加简洁，适合用于设计和描述，DFA 则适合于实现和执行。

有穷自动机的应用：

1. 正则表达式匹配：

   • 有穷自动机是正则表达式的核心理论基础。正则表达式可以转换为 NFA 或 DFA，然后使用自动机来匹配字符串。

2. 词法分析：

   • 编译器中的词法分析器（Lexer）使用 DFA 或 NFA 来识别输入源代码中的单词（例如，关键字、变量名、操作符等）。

3. 文本搜索：

   • 在文本搜索中，使用有穷自动机来高效匹配模式串和目标文本。

4. 控制系统：

   • 有穷自动机在许多实际应用中，如硬件设计中的状态机、流程控制、网络协议等，广泛用于描述和实现状态转移。