相关正则语言之间的泵长关系

Question

一种常规语言的抽运长度与一种相关语言的抽运长度有何关系？例如，如果A，:<，B，:<，C都是正则语言，k是B的抽运长度，我们知道A和C的抽运长度吗？

人们可能会天真地认为，当我们查看有限语言时，子语言具有较小的(<=)泵送长度。{a，ab，abc} :< {a，ab，abc，abcd}有各自的抽运长度4 <= 5。从集合中抽取一个元素不能使其最长的单词更长。

另一方面，如果您查看由两种语言的同步乘积形成的状态机，交集语言和联合语言具有相同的状态机结构，但不同之处在于交集的最终状态集是联合的最终状态集的子集。拥有更多的最终状态，可以使找到通过状态机的更短路径的可能性更大。但相反，具有更少的最终状态会使状态机更有可能具有不可共访问的状态，因此是可减少的。

Answer 1

首先请注意，一个字母表上的所有语言都通过某种关系与该字母表上的所有其他语言相关，尽管是人为设计的。我们真的需要像您建议的那样，将讨论限制在像subset这样的东西上，以便有意义地确定问题的范围。

现在，您已经正确地注意到，在一般情况下，subset关系与相关语言的长度没有明显的关系。您可以很容易地将a*与{a^n}进行比较，并表明a*的最小可伸缩性几乎总是比{a^n}的要简单。

让我们进一步限制自己使用条目数量有限的语言；也就是说，L \ R是有限的，而R \ L是有限的。这是一个不同于subset的相似性指示器；但是如果我们要求R \ L为空，那么我们将恢复subset的受限版本。我们现在可能会问同样的问题:对于条目数量有限的不同语言，subset关系是否能告诉我们什么？

答案仍然是否定的。考虑L = a*和R = a* \ A，其中A是a*的有限非空子集。尽管如此，L需要一种状态，而R可能需要更多状态。

将自己限制在有限集上，正如您所建议的，确实让我们推导出您的建议：R的最小自动机不会比L的自动机具有更多的状态。为什么会这样呢？我们必须有n+1状态才能接受任何长度为n的字符串，并且我们必须有一个死状态才能接受不是该语言的字符串(其中将有无限多个)。如果语言是有限的，那么最小的DFA将根本没有循环(除了以死状态为中心)，否则您将能够获得无限多的字符串。

你对笛卡尔乘积的观察是正确的，因为应用构造的结果为任何集合操作(并集、差分、交集等)提供了结构上相同的DFA；然而，这些DFA不能保证是最小的，有限语言的点仍然有效，即在两台机器的DFA最小化之前和之后，交集的DFA不会比并集的DFA具有更多的状态。

您也许能够利用Myhill-Nerode定理，并使用它来定义“密切相关”的概念，这确实允许您比较语言，以确定哪种语言将具有更大、最小的DFA。然而，我不确定这一点，因为这样做的一种简单方法将允许您将其与参数化参考语言进行比较，例如，轻松地证明任何非正则语言是非正则语言，这在数学上可能是一个大问题(例如，要么在一般情况下是不可能的，要么它将证明P=NP等)。