regular-language - 任何常规语言 L 都有无限的单词吗？

Question

这很奇怪，但通过抽引理，说

让我们L成为一种常规语言。存在一个常数n，使得对于这样的每个字符串，w我们都可以闯入也在 中的这样。L|w| >= nwxyzxy*zL

这个引理很强大，因为它适用于所有常规语言。但是如果是常规语言L = a呢？里面只有一个字（a）。在这种情况下，抽水引理如何工作？

Answer 1

如果n = 2那么任何win Lwith|w| >= n满足抽水引理的结论都是空洞的。中的任何文字L都不足以作为反例。更一般地，如果L是任何有限语言，则L满足抽水引理：只需n大于 中最长单词的长度L。