何时对 DFA/NFA 中的状态使用 Ø
When to use Ø for states in DFA / NFA
我对 DFA / NFA 中“Ø”的用法感到困惑（让我们在 DFA 到 NFA 转换的上下文中讨论这个问题）
假设我有一个 NFA，如下所示：
enter image description here
没有为状态 1 的符号“a”定义任何转换。所以在转换中 table 我会写与“Ø”相同的转换还是写“1”原因它将保持状态“1”，因为它没有任何转换箭头
会不会是这样：
| state | a | b | E |
|----------------|----------|-------|---------|
| 1 | Ø | {2} | {3} |
| 2 | {2,3} | {3} | Ø |
| 3 | {1} | Ø | Ø |
或：
| state | a | b | E |
|----------------|----------|-------|---------|
| 1 | {1} | {2} | {3} |
| 2 | {2,3} | {3} | {2} |
| 3 | {1} | {3} | {3} |
选择使用“Ø”会影响最终输出。现在，我们可以构建状态的幂集，然后计算 epsilon clousure，但让我们把它缩短，我们将直接看一个有争议的状态，它可能会或可能不会出现在最终的 DFA 中，我们将尝试使用“Ø”而不使用“Ø”
(1) 不使用 null: ( Table 2 )
州 = {1,2}
从 1 和 2，收到 a 我们去 1,2,3
epsilon 闭包 (1,2,3) = 1,2,3
(2) 使用空值：( Table 1 )
州 = {1,2}
从 1 和 2，收到 a 我们转到 {2,3}
epsilon 闭包 (2,3) = 1,2,3
现在，过渡可能看起来相同，但在某些情况下，我们会再次以我们无处可去但保持相同状态的状态结束，如果我们选择使用“Ø”，那么我们在最终输出“Ø”中会有一个额外的状态。在这种情况下，它只是意味着如果我们没有某个符号的转换，那么我们会进入这个状态
但如果我们不这样做，那么我们的最终输出将不会有额外的状态“Ø”。在这里，如果我们不为某个符号指定转换，我们就不会为它指定转换箭头，就像图中状态 1 中的符号“a”一样
那么，哪一个是正确的，一个没有状态“Ø”，一个有状态“Ø”
带Ø的那个。考虑一个简单的 NFA：
/-> S -a-> (T)
| |
\-a-/
S为起始状态，T为接受状态。字母表是{a, b}。
当本机读取字符串 b 时，它会拒绝。如果 (S, b) 的转换集是 {S}，那么这个转换成的 DFA 将接受 ba，这显然是错误的。
正确的过渡状态如下：
S, a, {S, T}
S, b, Ø
{S, T}, a, {S, T}
{S, T}, b, Ø
Ø, a, Ø
Ø, b, Ø
你可以用两种方式绘制这个 DFA。不完整的 DFA（空状态被省略）或完整的 DFA（空状态作为不可避免的状态存在）。 q1 = {S}，开始状态，q2 = {S, T}，接受状态。
Incomplete:
q1 -a-> (q2)<-\
| |
\-a-/
Complete:
/a,b\
| /
\ v
/-> q3 <-\
b b
| |
q1 -a-> (q2)<-\
| |
\-a-/
请注意，在完整版本中，q3 与 Ø 具有相同的属性。
（一般来说，一个不完整的 DFA 总是可以用这种方式替换为一个完整的 DFA：创建一个新的 non-accepting 状态 d，其输出转换为 d, Σ, d，并且其传入转换是原始 DFA 中缺少的任何转换。d 是“转储”状态，可以被认为是“拒绝”状态而不是接受状态。一旦输入进入该状态状态，它没有接受的途径，因此可以被拒绝。）
我对 DFA / NFA 中“Ø”的用法感到困惑（让我们在 DFA 到 NFA 转换的上下文中讨论这个问题）
假设我有一个 NFA，如下所示： enter image description here
没有为状态 1 的符号“a”定义任何转换。所以在转换中 table 我会写与“Ø”相同的转换还是写“1”原因它将保持状态“1”，因为它没有任何转换箭头
会不会是这样：
| state | a | b | E |
|----------------|----------|-------|---------|
| 1 | Ø | {2} | {3} |
| 2 | {2,3} | {3} | Ø |
| 3 | {1} | Ø | Ø |
或：
| state | a | b | E |
|----------------|----------|-------|---------|
| 1 | {1} | {2} | {3} |
| 2 | {2,3} | {3} | {2} |
| 3 | {1} | {3} | {3} |
选择使用“Ø”会影响最终输出。现在，我们可以构建状态的幂集，然后计算 epsilon clousure，但让我们把它缩短，我们将直接看一个有争议的状态，它可能会或可能不会出现在最终的 DFA 中，我们将尝试使用“Ø”而不使用“Ø”
(1) 不使用 null: ( Table 2 )
州 = {1,2}
从 1 和 2，收到 a 我们去 1,2,3
epsilon 闭包 (1,2,3) = 1,2,3
(2) 使用空值：( Table 1 )
州 = {1,2}
从 1 和 2，收到 a 我们转到 {2,3}
epsilon 闭包 (2,3) = 1,2,3
现在，过渡可能看起来相同，但在某些情况下，我们会再次以我们无处可去但保持相同状态的状态结束，如果我们选择使用“Ø”，那么我们在最终输出“Ø”中会有一个额外的状态。在这种情况下，它只是意味着如果我们没有某个符号的转换，那么我们会进入这个状态
但如果我们不这样做，那么我们的最终输出将不会有额外的状态“Ø”。在这里，如果我们不为某个符号指定转换，我们就不会为它指定转换箭头，就像图中状态 1 中的符号“a”一样
那么，哪一个是正确的，一个没有状态“Ø”，一个有状态“Ø”
带Ø的那个。考虑一个简单的 NFA：
/-> S -a-> (T)
| |
\-a-/
S为起始状态，T为接受状态。字母表是{a, b}。
当本机读取字符串 b 时，它会拒绝。如果 (S, b) 的转换集是 {S}，那么这个转换成的 DFA 将接受 ba，这显然是错误的。
正确的过渡状态如下：
S, a, {S, T}
S, b, Ø
{S, T}, a, {S, T}
{S, T}, b, Ø
Ø, a, Ø
Ø, b, Ø
你可以用两种方式绘制这个 DFA。不完整的 DFA（空状态被省略）或完整的 DFA（空状态作为不可避免的状态存在）。 q1 = {S}，开始状态，q2 = {S, T}，接受状态。
Incomplete:
q1 -a-> (q2)<-\
| |
\-a-/
Complete:
/a,b\
| /
\ v
/-> q3 <-\
b b
| |
q1 -a-> (q2)<-\
| |
\-a-/
请注意，在完整版本中，q3 与 Ø 具有相同的属性。
（一般来说，一个不完整的 DFA 总是可以用这种方式替换为一个完整的 DFA：创建一个新的 non-accepting 状态 d，其输出转换为 d, Σ, d，并且其传入转换是原始 DFA 中缺少的任何转换。d 是“转储”状态，可以被认为是“拒绝”状态而不是接受状态。一旦输入进入该状态状态，它没有接受的途径，因此可以被拒绝。）