为什么常规语言的补充仍然是常用语言？

Question

根据我的教科书,L1 = A* - L1的补语是常规语言,只要L1是常规语言.
A*不包括Context Free语言,Context Sensitive语言和Recursively Enumerable语言吗？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*不能也不能"包含语言",因为它是一组字符串.

对于你的第二个问题:

另外,A* - L1 = A*交叉补码(L1).是不是用补语定义的一个补语定义了一个补语？

好问题.我怀疑这是作为定义呈现的,这只是定义运算符-.据我所知,它没有定义"补充功能".也许已经定义了"补语",你的书现在正试图定义减法运算符.否则这是一个定理而不是定义.