从 RE 构建 FA
我们可以使用汤普森构造从正则表达式中找出有限自动机。我们将把正则表达式简化为最小的正则表达式，并将它们转换为 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 − 1 (0 + 1)* 0 的 NDFA。如果要将其转换为 DFA，只需应用第 1 章中讨论的将 NDFA 转换为 DFA 的方法即可。
具有零移动的有限自动机 (NFA-ε)
具有零移动的有限自动机 (FA-ε) 不仅在给出字母集的输入后而且在没有任何输入符号的情况下进行传输。这种没有输入的转换称为空移动。
NFA-ε 形式上由 5 元组 (Q, Σ, δ, q 0 , F) 表示，包括
Q - 有限状态集
Σ − 一组有限的输入符号
δ − 转移函数 δ : Q × (Σ ∪ {ε}) → 2 Q
q 0 − 初始状态 q 0 ∈ Q
F - Q 的一组最终状态/状态 (F⊆Q)。
上面的(FA-ε)接受一个字符串集 − {0, 1, 01}
从有限自动机中去除空移动
如果在 NDFA 中，顶点 X 到顶点 Y 之间存在 ϵ-move，我们可以使用以下步骤删除它 -
- 找出 Y 的所有出边。
- 复制从 X 开始的所有这些边，而不更改边标签。
- 如果X是初始状态，则使Y也为初始状态。
- 如果 Y 是最终状态，则使 X 也成为最终状态。
问题
将以下 NFA-ε 转换为无空移动的 NFA。
解决方案
步骤 1 -
这里，ε 跃迁位于q 1和q 2之间，因此令q 1为X，q f为Y。
这里，对于输入 0 和 1，从 q f到 q f的出边。
步骤 2 -
现在我们将复制 q 1中的所有这些边，而不更改 q f中的边，并得到以下 FA -
步骤 3 -
这里q 1是一个初始状态，所以我们令q f也是一个初始状态。
所以 FA 变成 -
步骤 4 -
这里 q f是最终状态，所以我们使 q 1也是最终状态。
所以 FA 变成 -
