寻找确定有限状态自动机的补集？

Question

寻找确定有限状态自动机的补集？

regexregular-languageautomatadfanfa

18

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

然而，正则表达式的初始接受状态似乎为{00，1，^}，最终接受状态也是如此。{00，1，^}。因此，交换它们将导致完全相同的正则表达式和DFA，这似乎是矛盾的。

我是否做错了什么，还是这个正则表达式不应该有真正的补集？

谢谢

- Matt Hintzke

此外，为了补充DFA，您只需交换每个状态的“最终性”--也就是说，使每个非最终状态成为最终状态，每个最终状态成为非最终状态。 - aaaaaa123456789

那初始状态不能是00或1吗？ - Matt Hintzke

并不是真的--请记住，初始状态是它开始读取字符串的地方，因此到目前为止它还没有读取任何内容。但是有从它出发的00和1的转换。也许你应该查一些DFA的信息？ - aaaaaa123456789

我理解。从技术上讲，它开始为空字符串，然后可以读取00或1。但这不会改变我的困境。 - Matt Hintzke

实际上是可以的。无论如何，正如我所说，您不必触及初始状态（它仍然是相同的）-- 您只需要使每个最终状态变为非最终状态，每个非最终状态变为最终状态。如果您简化了DFA（使用了最少的状态），那么您应该只有1个最终状态（即初始状态）和1-2个非最终状态--如果是这种情况，请将初始状态设置为非最终状态，其余状态设置为最终状态。 - aaaaaa123456789

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Grijesh Chauhan · 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

如何找到 DFA 的补集？

定义：语言的补集是通过与 Σ*（sigma star）的差集来定义的，即 L^' = Σ^* - L。

补集语言(L^')是由Σ* (sigma star)中除了L中的字符串组成的。Σ*包含了字母表Σ中所有可能的字符串。
_{Σ = 语言符号集合}

要构建接受补集L的DFA D，只需要将A中的每个接受状态转换为D中的非接受状态，并将A中的每个非接受状态转换为D中的接受状态。
(注意！对于NFA不适用)

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

注意：要构建补集DFA，旧的DFA必须是完整的，也就是说每个状态都应该有可能的出边(或者换句话说δ应该是一个完整的函数)。

补充：附带示例的参考

为正则表达式(00+1)*构建DFA

下面是名为A的DFA：

但是这个DFA并不完整。转移函数δ是部分定义的，而不是针对完整域Q×Σ（q1缺少标签为1的出边）。它的完整DFA可以如下所示（A）：

在上述DFA中，定义了所有可能的转换（*对于每一对*），并且在这种情况下δ是一个完全函数。参考文献：学习什么是部分函数。通过将所有终止状态q0更改为非终止状态，反之亦然，可以构造新的补充DFA D。

因此，在补充中，q0变成非最终状态，q1，q2是最终状态。

现在你可以使用我提供的ARDEN'S THEOREM和DFA编写补集语言的正则表达式。

这里我直接为补集编写正则表达式： (00 + 1)* 0 (^ + 1(1 + 0)*) 其中^是空符号。

一些有用的链接：
你可以从这里和我的个人资料中找到更多关于FA的有用答案。此外，还有两个关于正则语言属性的好链接：一个，第二个