为什么正则语言的补语仍然是正则语言？
根据我的教科书，只要 L1 是正则语言，L1 = A* - L1 的补集就是正则语言。
A* 不是还包括上下文无关语言、上下文相关语言和递归可枚举语言吗？ A*-L1 也将包括所有这些，不是吗？那怎么可能有规律呢？
在有限状态机的表示下，我理解为什么补码仍然是常规语言。但是，我无法理解其背后的理论。
另外， A* - L1 = 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.
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.
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我认为您感到困惑的地方是，当您说“A* 不是还包括上下文无关语言、上下文敏感语言和递归可枚举语言吗？”时，您会感到困惑。您混淆了
A*（一组字符串）和Powerset(A*)（一组语言） 。确实，
Powerset(A*) - {L1}是一个包含“上下文无关语言、上下文敏感语言和递归可枚举语言”的集合，但它实际上与定理无关，即说：给定任何常规语言L（一组字符串），则语言A*-L（也是一组字符串）是也是一种常规语言。TL;DR 您的问题中的级别之间存在混淆：字符串集与语言集。
A*分为L和A*-L的任何两部分，其中L是正则，也必须有A*-L常规。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 confusingA*, which is a set of strings, withPowerset(A*), which is a set of languages.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 languageL(a set of strings), then the languageA*-L, also a set of strings, is also a regular language.TL;DR there's a confusion between levels in your question: sets of strings vs. sets of languages. Any two-partition of
A*intoLandA*-Lin whichLis regular must also haveA*-Lregular.A*does not and cannot "contain languages" because it is a set of strings.To your second question:
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.我找不到我的 Hopcroft & 的副本Ullman，但我认为我找到了常规语言补语的正确定义此处。说 L 的补集是一个 DFA，它接受除属于 L 的成员之外的任何字符串，这似乎是正确的，并且在对话中更清楚。因此，您移动接受状态致所有（以前）不接受的国家，您就完成了。由于补码只是 DFA 的排列，因此结果仍然是 DFA。
就符号而言，我认为您将其读作
L1 = A* - L1，而它应该正确地读作complement L1 = A* - L1，其中< code>complement 是补码运算符。I can't find my copy of Hopcroft & Ullman, but I think I found the correct definition for the complement of a regular language here. It seems correct and more conversationally clear to say that the complement of L is a DFA that accepts any string except those that are a member of L. So you move the accepting state to all (formerly) non-accepting states and your are done. Since the complement is just a permutation of the DFA, the result is still a DFA.
As far as the notation goes, I think you are reading it as
L1 = A* - L1when it should be properly read ascomplement L1 = A* - L1wherecomplementis the complement operator.如果你能理解自动机证明，那么你就拥有了一切。其背后的直觉是，如果您可以通过运行自动机并查看它是否停止在最终状态来识别常规语言，那么您只需运行相同的自动机就可以识别该语言的补集（在所有字符串的集合上）并查看是否停止在非最终状态。由于所有字符串都停止在某种状态上，并且当且仅当语言停止在最终状态时才是常规语言，因此当且仅当它停止在非最终状态时它才是非常规语言。我想这非常直观。此外，您需要向自己证明一种语言是常规语言的唯一一件事就是为其构建一个自动机：只需交换所有最终状态和非最终状态即可。
If you can understand the automaton proof, then you have it all. The intuition behind it is that if you can recognize a regular language by running an automaton and seeing if it stops on a final state, then you can recognize the complement of that language (over the set of all strings) just by running the same automaton and seeing if stops on a non-final state. Since all strings stop on some state, and a language is regular if and only if it stops on a final state, then it is non-regular if and only if it stops on a non-final state. It's pretty intuitive, I guess. Also, the only thing you need to prove to yourself that a language is regular, is building an automaton for it: just swap all final and non-final states.