从 RE 构造 FA

我们可以使用 Thompson 构造法从正则表达式中找出有限自动机。我们将正则表达式简化为最小的正则表达式，并将它们转换为 NFA，最后转换为 DFA。

一些基本的 RA 表达式如下 −

情况 1 − 对于正则表达式"a"，我们可以构造以下 FA −

情况 2 −对于正则表达式'ab'，我们可以构造以下 FA −

案例 3 − 对于正则表达式 (a+b)，我们可以构造以下 FA −

案例 4 −对于正则表达式 (a+b)*，我们可以构造以下 FA −

方法

步骤 1 根据给定的正则表达式构造具有 Null 移动的 NFA。

步骤 2 从 NFA 中删除 Null 转换并将其转换为其等效 DFA。

问题

将以下 RA 转换为其等效 DFA − 1 (0 + 1)* 0

解决方案

我们将连接三个表达式"1"、"(0 + 1)*"和"0"

现在我们将删除 ε 个转换。从 NDFA 中删除 ε 个转换后，我们得到以下 −

它是与 RE − 对应的 NDFA 1 (0 + 1)* 0。如果要将其转换为 DFA，只需应用第 1 章中讨论的将 NDFA 转换为 DFA 的方法即可。

具有零移动的有限自动机 (NFA-ε)

具有零移动的有限自动机 (FA-ε) 不仅在从字母集输入后转换，而且在没有任何输入符号的情况下转换。这种没有输入的转换称为 零移动。

NFA-ε 正式表示为 5 元组 (Q, ∑, δ, q₀, F)，由

• Q − 一组有限的状态

• ∑ −一组有限的输入符号

• δ − 一个转换函数 δ : Q × (∑ ∪ {ε}) → 2^Q

• q₀ − 一个初始状态 q₀ ∈ Q

• F − 一组 Q 的最终状态/状态 (F⊆Q)。

上述 (FA-ε) 接受字符串集 − {0, 1, 01>

从有限自动机中移除空移动

如果在 NDFA 中，顶点 X 到顶点 Y 之间存在 ϵ 移动，我们可以使用以下步骤将其移除 −

• 从 Y 找到所有传出的边。
• 从 X 开始复制所有这些边，而不更改边标签。
• 如果 X 是初始状态，则使 Y 也成为初始状态。
• 如果 Y 是最终状态，则使 X 也成为最终状态。

问题

将以下 NFA-ε到没有 Null move 的 NFA。

解决方案

步骤 1 −

这里 ε转换在 q₁ 和 q₂ 之间，因此让 q₁ 为 X 而 q_f 为 Y。

这里，对于输入 0 和 1，q_f 的传出边到 q_f。

步骤 2 −

现在我们将从 q₁ 复制所有这些边，而不更改来自 q_f 的边，并得到以下 FA −

步骤 3 −

这里 q₁ 是初始状态，因此我们将 q_f 也设为初始状态。

因此 FA 变为 −

步骤 4 −

这里 q_f 是最终状态，因此我们将 q₁ 也设为最终状态。

因此 FA 变为 −