有限状态机

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

一个有限自动机包括以下内容

Q：有限状态集
∑：有限输入符号集
q0：初始状态
F：最终状态
δ：状态转换函数

状态转换函数可以定义为

有限自动机的操作步骤

以下是在有限自动机上操作的步骤

• 首先，将有限状态机设置为起始状态。
• 如果字符串结束，则停止。
• 读取一个符号。
• 根据当前状态和读取的符号更新状态。
• 转到步骤 2

有限自动机的表示

• 最简单的表示通常是一个图
• 节点 = 状态
• 弧线表示状态转换
• 从状态 p 到 q 的弧线标记为所有那些已从 p 转换为 q 的输入符号。
• 弧线上的标签指示导致转换的原因。
• 标记为“开始”的箭头开始转换。
• 最终状态由双圆圈表示。

有限自动机的应用

• 它被用作设计和测试数字电路行为的软件。
• 典型编译器的词法分析器。
• 它被用作扫描大量文本以查找模式的软件。
• 用于验证具有有限状态的各种系统的软件。

例如： 股票市场交易。

有限自动机的例子

对单词“then”的识别进行建模

字符串穿过机器。如果从 then 获得一个字母，它将穿过机器，不会传递任何其他字母。

有限自动机的组成部分

以下是有限自动机的组成部分的列表

• 输入磁带包含一个字符串。
• 磁头一次读取一个输入字符串符号。
• 内存位于有限数量的位置之一。

状态转换图

• 它被理解为一种语言识别算法的流程图。
• 它是一个集合
  • 一个有限的状态集，其中一个被选为初始状态，其中一些被指定为最终状态。
  • 由可能输入符号组成的字母表集合，输入字符串由这些字母表形成。
  • 一个有限的状态转换集，显示了给定状态在给定输入下的状态变化

通过转换图的成功路径是从初始状态开始并在其中一个最终状态结束的一系列边形成的路径。

FA 以两种方式为特征

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

DFA

DFA 代表 确定性有限自动机。 Deterministic 指的是计算的唯一性。 在 DFA 中，输入字符只转到一个状态。 DFA 不接受空移动，这意味着 DFA 无法在没有任何输入字符的情况下更改状态。

DFA 有五个元组 {Q, ∑, q0, F, δ}

示例

查看确定性有限自动机的示例

转移表

NDFA

NDFA 指的是 非确定性有限自动机。 它用于转换特定输入的任意数量的状态。 NDFA 接受空移动，这意味着它可以在不读取符号的情况下更改状态。 对于给定的输入，从当前状态到下一个状态有许多路径。 为给定语言构造 DFA 很容易。

NDFA 也有五个状态，与 DFA 相同。 但 NDFA 有一个不同的状态转换函数。

NFA 是否与 DFA 一样强大？

NFA 可以完成 DFA 可以做的所有事情。 它不能做更多的事情。

一个语言 L 被 DFA 接受，当且仅当它被 NFA 接受。

NDFA 的状态转换函数可以定义为

示例

查看非确定性有限自动机的示例

状态转换图

转移表

确定性有限自动机和非确定性有限自动机的区别

关于有限状态机的常见问题解答

1. 您对 DFA 中的死状态是什么意思？

答案： 如果一台机器成功接受最终字符串，则该字符串被 DFA 接受。 但有时，机器无法再进入其最终状态，那么我们就达到了死状态。

2. 有限状态机是什么意思？

答案： 有限状态机是有限数量的状态的集合，并且根据输入符号在这些状态之间进行转换。

3. 为以下状态转换表创建一个 NDFA.

示例

答案

将转换表转换为转换图的步骤如下

• 图中的状态用顶点表示。
• 弧线由表示图中转换的输入字符表示。
• 初始状态用箭头标记。
• 最终状态在图中用双圆圈表示。

以下是转换表的图解表示

输入状态集 (Q) = {q0, q1, q2, q3}

字母集 (∑ )= {0, 1}

初始状态 (q0 )= {q0}

最终状态 (F )= {q3}