从 DFA 中删除或添加空词
Removing or adding the empty word from a DFA
标题是我对这个问题的解读。以下是我到目前为止所做的尝试：
情况一：Ɛ∈L(M)
L(M1) = L(M)
L(M2) = {Q2, Σ2, q20, F2, 2}
Q={q0, ..., qi}
Q2={q20, ... , q2i+1}
Σ2 = Σ
q2i+1 ∈ F2 当且仅当 q i ∈ F
2(q2i+1, a) = (qi, a)
情况2：Ɛ∉L(M)
L(M2) = L(M)
L(M1) = {Q1,Σ1,q10, F1, 1}
...
到目前为止，您的内容看起来不错但不完整。这是对剩下的内容的描述；用符号写出来留作练习。
在第一种情况下，如果语言已经包含空字符串，我们就完成了，可以直接使用该语言的自动机，无需修改。如果它不包含空字符串，我们可以添加一个新的初始状态并让它像原始初始状态一样转换。如果我们不理会所有其他转换并让这个新的初始状态接受，我们将接受空字符串以及原始自动机接受的任何内容。
在第二种情况下，如果该语言还没有包含空字符串，我们就完成了，可以直接使用该语言的自动机，无需修改。如果它确实已经包含空字符串，我们可以添加一个新的初始状态并让它像原始初始状态一样转换。如果我们不理会所有其他转换并且不接受这个新的初始状态，我们将不会接受空字符串但会继续接受其他所有内容。
一般来说，这是可以做到的最好的。但是，特定语言的自动机可能比添加或删除空字符串后构造的自动机更小。例如，仅由空字符串组成的语言有一个具有两种状态的 DFA，但是删除了空字符串的该语言的最小 DFA 有一个状态。类似地，所有非空字符串的语言都有一个具有两种状态的 DFA，但是将空字符串添加到该语言意味着该语言有一个单状态 DFA。所以这个构造并不总是给出尽可能小的 DFA，但它保证适用于所有情况，包括那些没有针对该语言的更小 DFA 的情况（例如，将空字符串添加到空语言强制添加一个新的州）。
标题是我对这个问题的解读。以下是我到目前为止所做的尝试：
情况一：Ɛ∈L(M)
L(M1) = L(M)
L(M2) = {Q2, Σ2, q20, F2, 2}
Q={q0, ..., qi}
Q2={q20, ... , q2i+1}
Σ2 = Σ
q2i+1 ∈ F2 当且仅当 q i ∈ F
2(q2i+1, a) = (qi, a)
情况2：Ɛ∉L(M)
L(M2) = L(M)
L(M1) = {Q1,Σ1,q10, F1, 1}
...
到目前为止，您的内容看起来不错但不完整。这是对剩下的内容的描述；用符号写出来留作练习。
在第一种情况下，如果语言已经包含空字符串，我们就完成了，可以直接使用该语言的自动机，无需修改。如果它不包含空字符串，我们可以添加一个新的初始状态并让它像原始初始状态一样转换。如果我们不理会所有其他转换并让这个新的初始状态接受，我们将接受空字符串以及原始自动机接受的任何内容。
在第二种情况下，如果该语言还没有包含空字符串，我们就完成了，可以直接使用该语言的自动机，无需修改。如果它确实已经包含空字符串，我们可以添加一个新的初始状态并让它像原始初始状态一样转换。如果我们不理会所有其他转换并且不接受这个新的初始状态，我们将不会接受空字符串但会继续接受其他所有内容。
一般来说，这是可以做到的最好的。但是，特定语言的自动机可能比添加或删除空字符串后构造的自动机更小。例如，仅由空字符串组成的语言有一个具有两种状态的 DFA，但是删除了空字符串的该语言的最小 DFA 有一个状态。类似地，所有非空字符串的语言都有一个具有两种状态的 DFA，但是将空字符串添加到该语言意味着该语言有一个单状态 DFA。所以这个构造并不总是给出尽可能小的 DFA，但它保证适用于所有情况，包括那些没有针对该语言的更小 DFA 的情况（例如，将空字符串添加到空语言强制添加一个新的州）。