从 A 构造一个新的 DFA B，其中 L(B) = L(A) - {w | w∈E* }
Construct a new DFA B from A where L(B) = L(A) - {w | w∈E* }
我对以下问题有点困难：
给定一个 DFA A = (E = {a,b,c} , Q ,q0 ,F , l)（其中 l 是转换函数），构建一个新的 DFA B 使得 L(B) = L(A) - {a}.
现在我明白了 Eb = Ea，但是我如何在不知道 A 的接受状态的情况下定义 B 转换函数或接受状态？
谢谢。
首先，让我们构建一个名为 C 的 DFA，它接受 w。这个 DFA 有 |w| + 2种状态：一种初始状态，一种死亡状态，一种接受状态。
其次，让我们构建一个名为 D 的 DFA，它接受除 w 之外的所有内容。只需将所有非接受状态更改为接受状态，反之亦然。
第三，让我们在输入 DFA A 和 D 上使用笛卡尔乘积机构造以交集作为运算符来构造 B。这个 DFA 将有 |Q|总共 x (|w| + 2) 个状态。
B的语言是A和D同时接受的一切。 D 接受任何不是 w 的东西；因此，B 根据需要接受 L(A) 中不是 w 的任何内容。
编辑：关于 B 最终的样子的更多细节。
设A的状态为QA，D的状态为QD。设 A 的接受状态为 FA，D 的接受状态为 FD。令 dA 为 A 的转换函数，dD 为 D 的转换函数。根据我们上面的构造，我们有：
- Q = {(x, y) for x in QA y in QD}
- E = 与 A 和 D 相同的字母表，假设相同。如果 w 仅包含 A 字母表中的符号，则只需使用 A 字母表即可。如果 w 包含不在 A 的字母表中的符号，那么 w 不在 L(A) 中，我们可以让 B = A.
- q0 = (q0, q0')
- F = {(x, y) 在 Q | FA 中的 x 和 FD 中的 y}
- d((x, y), s) = (dA(x, s), dD(y, s))
至于D长什么样：
- QD = {q0', q1', …, q(|w|+1)'}
- E = 与 A 相同
- q0'为初始状态
- FD = QD \ {q(|w|)}
- d(qi, s) = q(i+1) 如果 s 是 w 的第 (i+1) 个符号，否则为 q(|w|+1)
我对以下问题有点困难：
给定一个 DFA A = (E = {a,b,c} , Q ,q0 ,F , l)（其中 l 是转换函数），构建一个新的 DFA B 使得 L(B) = L(A) - {a}.
现在我明白了 Eb = Ea，但是我如何在不知道 A 的接受状态的情况下定义 B 转换函数或接受状态？
谢谢。
首先，让我们构建一个名为 C 的 DFA，它接受 w。这个 DFA 有 |w| + 2种状态：一种初始状态，一种死亡状态，一种接受状态。
其次，让我们构建一个名为 D 的 DFA，它接受除 w 之外的所有内容。只需将所有非接受状态更改为接受状态，反之亦然。
第三，让我们在输入 DFA A 和 D 上使用笛卡尔乘积机构造以交集作为运算符来构造 B。这个 DFA 将有 |Q|总共 x (|w| + 2) 个状态。
B的语言是A和D同时接受的一切。 D 接受任何不是 w 的东西；因此，B 根据需要接受 L(A) 中不是 w 的任何内容。
编辑：关于 B 最终的样子的更多细节。
设A的状态为QA，D的状态为QD。设 A 的接受状态为 FA，D 的接受状态为 FD。令 dA 为 A 的转换函数，dD 为 D 的转换函数。根据我们上面的构造，我们有：
- Q = {(x, y) for x in QA y in QD}
- E = 与 A 和 D 相同的字母表，假设相同。如果 w 仅包含 A 字母表中的符号，则只需使用 A 字母表即可。如果 w 包含不在 A 的字母表中的符号，那么 w 不在 L(A) 中，我们可以让 B = A.
- q0 = (q0, q0')
- F = {(x, y) 在 Q | FA 中的 x 和 FD 中的 y}
- d((x, y), s) = (dA(x, s), dD(y, s))
至于D长什么样：
- QD = {q0', q1', …, q(|w|+1)'}
- E = 与 A 相同
- q0'为初始状态
- FD = QD \ {q(|w|)}
- d(qi, s) = q(i+1) 如果 s 是 w 的第 (i+1) 个符号，否则为 q(|w|+1)