我想到了一个证明，但我不太确定它是否有效。
假设你必须证明以下语言的非正则性:
A = {0^n 1^n 2^n | n>= 0}
我设计的证明选择了一个属于该语言的字符串，比如012，并表明它与如何划分无关，抽水引理并不完全满足(我可以发布整个证明，但帖子是冗长的)。然而，根据我的教授，这个证明不能被接受。
他没有解释为什么，我不明白这样的证明如何不足以证明一种语言不是规则的。如果一个字符串显然属于一种假定的正则语言，却不满足抽运引理，那么该语言显然有不正则的字符串作为它的字符串集合的一部分，因此该语言不是正则的。
我相信我的教授拒绝这个证明的原因是因为在大多数问题中泵浦长度p不能被正确猜测。同时，我看不出我的证明怎么能用一个反例来证明是错误的。
如果语言是正则的并且p实际存在，则只能选择p(泵送长度)为特定的数字。事实上，你选择了一个确切的数字，这意味着p存在，这是需要实际证明的东西。
假设p存在。让我们选择一个足够长的词:w=0^{p}1^{p}2^{p}。根据抽运引理，A语言中的每个字符串都必须分解为w=xyz与|xy|≤p和|y|≥1，使得A语言中的xy^{i}z对应每个i≥0。为了满足|xy|≤p，选择x为空，y=0^{p}为空，z=1^{p}2^{p}为空。由引理，|y|≥1得到|xy|≥1。带有i≠1的字符串(在xy^{i}z中)不在A语言中。因此，该语言是非正则的，p不存在。
如果p存在，则可以为该语言构造有限状态自动机。但是不存在这样的自动机，因为它需要内存来记住0的数量，以便以后匹配1和2的相同数量。如果n是一个有限的数，那么你可以构造一个可能很大的自动机，但是对于无限的n，没有有限的自动机可以构造。
这种语言甚至不是上下文无关的，因为没有可以为它构造的下推自动化。它是上下文敏感的。