是常规设置的powerset也是常规组？

Question

如果是这样，我在哪里可以找到它的证据？如果没有，有一个反例吗？

通过常规语言的powerset，我的意思是常规语言的所有子集合。

谢谢你，马库斯。

Answer 1

no。在计算机科学中，语言通常被定义为 $ \ {0,1 \} ^ * $ 的子集。如果 $ l $ 是一种语言，那么powerset $ 2 ^ l $ 不是 $ \ {0,1 \} ^ * $ ，所以它不是一种语言。

（参见例如， https://en.wikipedia.org/wiki/formal_language#definition ）

如果 $ l $ 是有限的，那么powerset $ 2 ^ l $ 是有限的，所以<一个href=“https://cs.stackexchange.com/questions/123918/is-the-powerset-of-a-regular-set-also-a-regular-set/123919?nnoredirect=1#comment259677_123919”> EmilJežábek指出，有一种方法可以编码它，所以其编码是一种常规语言，因为所有有限语言都是常规的。

如果 $ l $ 是无限的，那么作为yuval filmus指向，powerset $ 2 ^ l $ 不是可计算的，因此无法将其作为一种语言编码。因此，当<跨度类=“math-container”> $ l $ 是一种无限常规语言时，那么您问题的答案是“否，即使您允许选择合理的编码即使您也不选择合理的编码”。