我正在上自动机理论课，现在我们正在学习抽水引理。有一个练习题要求我们“设计一种语言 L，使得 L 和它的补码都没有无限的正则子集？” 但我不明白这个问题。什么是无限正则子集？我应该如何找到可以满足此要求的语言？
任何人都可以对这个问题有所了解吗？
谢谢！
问问题
1596 次
2 回答
0
更准确地说，您需要找到一种语言L，使得它的子集不L存在无限正则语言，并且其补集的子集不存在L无限正则语言。
这是一个不正确的示例：L= 和 的a^n并集a^n b^n。由于a^n是常规语言并且它是 的子集L，因此这不适用于答案。
为了找到L符合要求的问题，我发现这类问题更像是谜题。你尝试一些事情，检查它们是否有效，并尝试思考为什么它们不能解决问题。最终，您会考虑这种情况并提出解决方案。
于 2011-01-22T04:05:41.637 回答
0
好吧，语言的无限规则子集是无限且规则的子集。好吧，这可能不是很有帮助。
所以“子集”很清楚。
“常规子集”是一个被确定性有限状态机接受的子集（实际上在语言理论中有一个惊人的定理，它说这个条件等同于少数其他条件）。
“无限集”是一个非有限的集合，或者等效地，一个具有无限多个元素的集合。
所以假设一种语言L是特殊的，如果它有一个无限的正则子集。
你的工作是找到一种语言L，使得两者L及其补语L都不特殊。
要解决这个问题，您需要先了解该定义。从您的笔记和文本中获取一些语言示例。弄清楚它们是否正常。如果你发现一个不是，想想是什么让它不规则，看看你是否设计了一种语言，它的所有无限子集都是不规则的。然后看看当你看它的补码时会发生什么。
你必须建立你的直觉，而做到这一点的唯一方法就是弄脏你的手。
于 2011-01-22T04:07:51.383 回答