regex - 寻找 DFA 的补码？

Question

我被要求展示 DFA 图和 RegEx 作为 RegEx 的补充(00 + 1)*。在上一个问题中，我必须证明 DFA 的补码是封闭的并且也是一个正则表达式，所以我知道要将 DFA M 转换为补码 M`，我只需要交换初始接受状态和最终接受状态。

但是，RegEx 的初始接受状态似乎是{00, 1, ^}，最终接受状态也是{00, 1, ^}如此。因此，交换它们只会导致完全相同的 RegEx 和 DFA，这似乎是矛盾的。

我做错了什么还是这个 RegEx 应该没有真正的补充？

谢谢

score 38 · Accepted Answer

正如你所说：

我知道要将 DFA M 转换为补码 M`，我只需要交换初始接受状态和最终接受状态。

它不是互补的，但你正在做类似语言的反转，而常规语言在反转下是封闭的。

DFA的逆转

什么是反转语言？

语言 L 的反转（表示为 L ^R）是由 L 中所有字符串的反转组成的语言。

假设 L 是某个 FA A 的 L(A)，我们可以为 L ^R构造一个自动机：

反转转换图中的所有边（弧）

L ^R自动机的接受状态是 A 的开始状态

为新自动机创建一个新的开始状态，其中 epsilon 转换到 A 的每个接受状态

注意：通过反转所有箭头并交换 DFA 的初始状态和接受状态的角色，您可能会得到 NFA。
_{这就是我写FA（不是DFA）的原因}

寻找 DFA 的补码？

Defination:语言的补语是根据与 Σ*（sigma 星）的集差来定义的。即 L ^' = Σ ^* - L。

L 的补语（L ^'）具有来自 Σ*（sigma 星）的所有字符串，除了 L 中的字符串。Σ* 是字母表 Σ 上的所有可能字符串。
_{Σ = 语言符号集}

要构造接受 L 的补码的 DFA D，只需将 A 中的每个接受状态转换为 D 中的非接受状态，并将 A 中的每个非接受状态转换为 D 中的接受状态。
（警告！这不是真的对于 NFA 的）

_{A是L的DFA，D是补码}

注意：要构建补充 DFA，旧 DFA 必须是完整的，意味着每个状态都应该有所有可能的出边（或者换句话说δ应该是完整的函数）。

正则表达式的补充 DFA(00+1)*

下面是名为A的 DFA ：

但不是这个 DFA 不是完整的 DFA。转换函数δ是部分定义的，但不是针对整个域定义的Q×Σ（从 q1 中丢失了 lable 的边缘1）。

其完整的 DFA 可以如下（A）：

在上面的 DFA 中，所有可能的交易都被定义（*for each pair of Q,Σ*）并且δ在这种情况下是一个完整的函数。

可以通过将所有最终状态更改为非最终状态来构建新的补码 DFA Dq0，反之亦然。

因此，补码q0成为非最终状态，并且q1, q2是最终状态。

现在您可以使用我给出 的 ARDEN 定理和 DFA为补语编写正则表达式。

这里我直接为补码写正则表达式：

(00 + 1)* 0 (^ + 1(1 + 0)*)

哪里^是空符号。

一些有用的链接：
从这里和通过我的个人资料，您可以在 FA 上找到一些更有用的答案。此外，关于常规语言属性的两个很好的链接：一，二