转换图

转换图或状态转换图是一个有向图，可以按如下方式构造：

• Q 中的每个状态都有一个节点，由圆圈表示。
• 如果 δ(q, a) = p，则存在从节点 q 到节点 p 的有向边，标签为 a。
• 在起始状态，有一个没有来源的箭头。
• 接受状态或最终状态用双圆圈表示。

转换图中使用的某些符号

以下是 DFA 如何运作的描述

1. 在 DFA 中，自动机的输入可以是任何字符串。 现在，将指针指向起始状态 q 并从左到右读取输入字符串 w，并根据转换函数 δ 移动指针。 我们可以一次读取一个符号。 如果字符串 w 的下一个符号是 a 并且指针位于状态 p，则将指针移动到 δ(p, a)。 当遇到输入字符串 w 的末尾时，指针位于某个状态 F。

2. 如果 r ∈ F，则称字符串 w 被 DFA 接受，这意味着输入字符串 w 已成功处理并且自动机到达其最终状态。 如果 r ∉ F，则称字符串被 DFA 拒绝。

示例 1

∑ = {0, 1} 的 DFA 接受所有以 1 开头的字符串。

解决方案

有限自动机可以使用转换图表示。 在上图中，机器最初处于起始状态 q0，然后在接收到输入 1 时，机器将其状态更改为 q1。 从 q0 接收到 0 时，机器将其状态更改为 q2，这是死状态。 从 q1 接收到输入 0、1 时，机器将其状态更改为 q1，这是最终状态。 可以生成的可能的输入字符串是 10, 11, 110, 101, 111......，这意味着所有字符串都以 1 开头。

示例 2

∑ = {0, 1} 的 NFA 接受所有以 1 开头的字符串。

解决方案

NFA 可以使用转换图表示。 在上图中，机器最初处于起始状态 q0，然后在接收到输入 1 时，机器将其状态更改为 q1。 从 q1 接收到输入 0、1 时，机器将其状态更改为 q1。 可以生成的可能的输入字符串是 10, 11, 110, 101, 111......，这意味着所有字符串都以 1 开头。