computer-science - 为什么正则语言的补语仍然是正则语言？

Question

根据我的教科书，只要 L1 是正则语言，L1 = A* - L1 的补码就是正则语言。
A* 不是还包括上下文无关语言、上下文敏感语言和递归可枚举语言吗？A*-L1 也会包括所有这些，不是吗？那怎么能有规律呢？
在有限状态机的表示下，我理解为什么补语仍然是一种常规语言。但是，我无法理解其背后的理论。

此外， A* - L1 = A* 交集补码(L1) 。用补语定义的东西定义补语不是重言式吗？我真的不明白这怎么可能有效。

谢谢。

Answer 1

我认为您感到困惑的是，当您说“不A*还包括上下文无关语言、上下文敏感语言和递归可枚举语言？”时 你很困惑A*，这是一组字符串，而Powerset(A*)，这是一组语言。

确实这Powerset(A*) - {L1}是一个包含“上下文无关语言、上下文敏感语言和递归可枚举语言”的集合，但它实际上与仅说的定理无关：给定任何常规语言L（一组字符串），然后是语言A*-L，也是一组字符串，也是一种常规语言。

TL; DR 您的问题的级别之间存在混淆：字符串集与语言集。A*intoL和A*-Lin的任何两个分区L是正则的也必须有A*-L正则。 A*不会也不能“包含语言”，因为它是一组字符串。

对于你的第二个问题：

此外， A* - L1 = A* 交集补码(L1) 。用补语定义的东西定义补语不是重言式吗？

好问题。我怀疑如果这是作为定义提出的，那只是定义 operator -。据我所知，它没有定义“补函数”。也许已经定义了“补码”，而您的书现在正在尝试定义减法运算符。否则这是一个定理而不是一个定义。

Answer 2

我找不到我的Hopcroft & Ullman副本，但我想我在这里找到了常规语言补全的正确定义。说 L 的补码是一个 DFA，它接受除了 L 的成员之外的任何字符串，这似乎是正确的，而且对话更清楚。因此，您将接受状态移动到所有（以前）不接受状态，您就完成了。由于补码只是 DFA 的排列，因此结果仍然是 DFA。

就符号而言，我认为您正在阅读它，因为L1 = A* - L1它应该被正确阅读，因为补码运算符complement L1 = A* - L1在哪里。complement

Answer 3

如果你能理解自动机证明，那么你就拥有了一切。它背后的直觉是，如果您可以通过运行自动机并查看它是否在最终状态停止来识别常规语言，那么您只需运行相同的自动机就可以识别该语言的补码（在所有字符串的集合上）并查看是否在非最终状态下停止。由于所有字符串都在某个状态下停止，并且当且仅当它在最终状态上停止时，语言才是正则的，那么当且仅当它在非最终状态上停止时，它才是非常规的。我猜这很直观。此外，您唯一需要向自己证明一种语言是规则的，就是为它构建一个自动机：只需交换所有最终状态和非最终状态。