Automata Theory 简明教程
Construction of an FA from an RE
我们可以使用汤普森构建法发现一个由正则表达式构造的有穷自动机。我们将正则表达式简化为最小的正则表达式，然后将这些表达式转换为 NFA，最后转换为 DFA。
一些基本的 RA 表达式为：
Case 1 －对于正则表达式“a”，我们可以构造以下 FA －
Case 2 − 对于正则表达式“ab”，我们可以构建以下 FA −
Case 3 − 对于正则表达式 (a+b)，我们可以构建以下 FA −
Case 4 − 对于正则表达式 (a+b)*，我们可以构建以下 FA −
Method
Step 1 根据给定的正则表达式构建一个带有空动作的 NFA。
Step 2 从 NFA 中删除空转换，并将其转换成等效的 DFA。
Problem
将以下 RA 转换成等效的 DFA − 1 (0 + 1)* 0
Solution
我们将三个表达式“1”、“(0 + 1)*”和“0”连接在一起
现在我们将删除 ε 转换。从 NDFA 中删除 ε 转换后，我们得到以下结果 −
它是与 RE − 1 (0 + 1)* 0 相对应的 NDFA。如果你想将其转换成 DFA，只需应用第 1 章中讨论的 NDFA 到 DFA 的转换方法。
Finite Automata with Null Moves (NFA-ε)
带有空动作的有限自动机 (FA-ε) 不仅在从字母集合提供输入后进行转换，还可以在没有输入符号的情况下进行转换。这种没有输入的转换称为 null move 。
NFA-ε 由一个 5 元组（Q、∑、δ、q0、F）正式表示，其中包括
-
Q − 一组有限的状态
-
∑ − 一组有限的输入符号
-
δ − 一个转换函数 δ：Q ×（∑ ∪ {ε}）→ 2Q
-
q0 − 一个初始状态 q0 ∈ Q
-
F − Q 的一组最终状态/状态（F⊆Q）。
上述 (FA-ε) 接受一个字符串集合 − {0, 1, 01}
Removal of Null Moves from Finite Automata
如果在 NDFA 中，存在从顶点 X 到顶点 Y 的 ϵ 动作，我们可以使用以下步骤将其删除 −
-
查找从 Y 出发所有出边。
-
从 X 开始复制所有这些边，而不会更改边标签。
-
如果 X 是初始状态，则使 Y 也为初始状态。
-
如果 Y 是终止状态，那么也使 X 成为终止状态。
Problem
将以下 NFA-ε 转换为没有空移动的 NFA。
Solution
Step 1 -
这里 ε 转换在 q1 和 q2 之间，所以让 q1 等于 X ，而 qf 等于 Y 。
这里从 qf 出发到 qf 的输出边针对输入 0 和 1。
Step 2 -
现在，我们将从 q1 复制所有这些边，而不会更改从 qf 分出的边，并获得以下 FA −
Step 3 -
这里 q1 是一个初始状态，所以我们也将 qf 设置为初始状态。
因此 FA 变成 −
Step 4 -
这里 qf 是一个终止状态，因此我们也将 q1 设置为终止状态。
因此 FA 变成 −
