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

Question

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

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

谢谢。

Answer 1

我认为您感到困惑的地方在于，当您说“A* 是否还包括上下文无关语言、上下文敏感语言和递归可枚举语言”时？你很困惑A* , 即 一组字符串 , 与 Powerset(A*) , 即 一套语言 .

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

TL; DR 在您的问题中，级别之间存在混淆:字符串集与语言集。 A*的任意两分区进入 L和 A*-L其中L是正规的也必须有A*-L常规的。 A*没有也不能“包含语言”，因为它是一组字符串。

你的第二个问题:

Also, A* - L1 = A* intersection complement(L1) . Isn't defining a complement with something defined by the complement a tautology?

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