有限自动机

• 有限自动机用于识别模式。
• 它将符号字符串作为输入，并相应地改变其状态。当找到所需的符号时，就会发生转换。
• 在转换时，自动机可以移动到下一个状态，也可以停留在同一状态。
• 有限自动机有两种状态，**接受状态**或**拒绝状态**。 当输入字符串成功处理，并且自动机到达其最终状态时，它将被接受。

FA 的正式定义

有限自动机是 5 元组 (Q, ∑, δ, q0, F) 的集合，其中

有限自动机模型

有限自动机可以用输入带和有限控制器表示。

**输入带:** 它是具有多个单元格的线性带。 每个输入符号都放置在每个单元格中。

**有限控制器:** 有限控制器决定接收来自输入带的特定输入后的下一个状态。 磁带读取器从左到右一个接一个地读取单元格，并且一次只读取一个输入符号。

自动机类型

有限自动机有两种类型

1. DFA（确定性有限自动机）
2. NFA（非确定性有限自动机）

1. DFA

DFA 指的是确定性有限自动机。 确定性指的是计算的唯一性。 在 DFA 中，机器对于特定的输入字符仅进入一个状态。 DFA 不接受空移动。

2. NFA

NFA 代表非确定性有限自动机。 它用于为特定输入传输任意数量的状态。 它可以接受空移动。

关于 DFA 和 NFA 的一些要点

1. 每个 DFA 都是 NFA，但 NFA 不是 DFA。
2. 在 NFA 和 DFA 中都可以有多个最终状态。
3. DFA 用于编译器中的词法分析。
4. NFA 更像是一个理论概念。