问题描述
根据我的教科书，L1的补语= A *-只要L1是常规语言，L1就是常规语言。
A *不包括上下文无关的语言，上下文敏感语言和递归枚举语言？ A * -L1也将包括所有这些，不是吗？
在有限状态机的表示下，我理解为什么补语仍然是常规语言。但是，我无法理解其背后的理论。
According to my textbook, the complement of L1 = A* - L1 is a regular language as long as L1 is a regular language.
Doesn't A* also include Context Free languages, Context Sensitive languages, and Recursively Enumerable languages? A*-L1 would include all of them too, wouldn't it? How can it be regular then?
Under the representation of a Finite State Machine I understand why the complement is still a regular language. However, I can't understand the theory behind it.
此外，A *-L1 = A *交集补（L1）。用补语定义的重语不是用补语来定义补语吗？我真的不明白这怎么可能有效。
Also, A* - L1 = A* intersection complement(L1) . Isn't defining a complement with something defined by the complement a tautology? I don't really understand how that can be valid.
谢谢。
推荐答案
我认为您感到困惑的是，当您说 A * 还不包括上下文无关语言，上下文敏感语言和递归可枚举语言吗？您会混淆一组字符串的 A * 和 Powerset（A *），这是一组语言。
I think where you are confused is that when you say "Doesn't A* also include Context Free languages, Context Sensitive languages, and Recursively Enumerable languages?" you are confusing A*, which is a set of strings, with Powerset(A*), which is a set of languages.
确实， Powerset（A *）-{L1 } 是一个包含上下文无关的语言，上下文敏感的语言和递归可枚举的语言的集合，但它实际上与定理无关，后者只是说：给定任何常规语言 L （一组字符串），则语言 A * -L 也是一组字符串
It is true that Powerset(A*) - {L1} is a set containing "Context Free languages, Context Sensitive languages, and Recursively Enumerable languages" but it actually isn't relevant to the theorem which just says: given any regular language L (a set of strings), then the language A*-L, also a set of strings, is also a regular language.
TL；在您的问题中，各个级别之间存在混淆：字符串集与语言集。 A * 分为 L 和 A * -L L 是常规的$ c>还必须具有 A * -L 常规。 A * 不能并且不能包含语言，因为它是一组字符串。
TL;DR there's a confusion between levels in your question: sets of strings vs. sets of languages. Any two-partition of A* into L and A*-L in which L is regular must also have A*-L regular. A* does not and cannot "contain languages" because it is a set of strings.
第二个问题：
好问题。我怀疑这是否表示为定义，即仅定义运算符-。据我所知，它没有定义补码功能。也许已经定义了补码，并且您的书现在正在尝试定义减法运算符。否则，这是一个定理，而不是定义。
Nice question. I suspect if this is presented as a definition, that is just defining operator -. It is not defining the "complement function" as far as I can tell. Perhaps "complement" was already defined, and your book is now trying to define the subtraction operator. Or else this is a theorem rather than a definition.
这篇关于为什么普通语言的补语仍然是普通语言？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！