computation-theory - 是否存在仅由 1 个元素组成的非 RE 语言？

Question

我在一本书（Hromkovic，通信复杂性和并行计算）中读到，有无限数量的非递归 - 可枚举（非 RE）语言仅由一个元素组成？但这可能吗？我认为对于非 RE（甚至不可判定）的语言，语言必须是无限的。

Answer 1

不，所有有限语言都是正则的，因为它们可以被有限自动机接受。对于您阅读的内容，至少有三种可能的解释：

1. 作者写了一些不同的东西，而您的释义不正确；
2. 作者写的东西与他们的意图不同，可能使用了草率的术语；
3. 由于对不属于他们专业的主题的误解，作者写了一些不正确的东西。

如果你引用相关的段落，就有可能探索这些选项中的哪一个最有可能。请注意，每个人都会犯错误——读书的人和写书的人都是一样的。另请注意，我使用作者而不是作者，因为这篇文章可能是由一位作者单独编写的，并且没有经过适当的审查。