为什么普通语言的补语仍然是普通语言？ [英] Why is the complement of a regular language still a regular language?

问题描述

根据我的教科书，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.

第二个问题：

另外，A *-L1 = A *交集补码（L1）。不是用补语定义的补语来定义补语吗？

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

好问题。我怀疑这是否表示为定义，即仅定义运算符-。据我所知，它没有定义补码功能。也许已经定义了补码，并且您的书现在正在尝试定义减法运算符。否则，这是一个定理，而不是定义。

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.

这篇关于为什么普通语言的补语仍然是普通语言？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！