如何证明如果一种语言是无限的，那么L中的单词长度没有上限？

Question

L是一种基于有限字母表的语言。如何证明如果L是无限的，那么L中的单词长度没有上限？

有人能帮我证明这一点吗。

Answer 1

假设L中单词的长度有一个上界= n。

让∑作为字母表。

因此长度为0的字符串数= |∑|^0 =1

长度为1的字符串数= |∑|^1

依此类推，直到长度为n= |∑|^n的字符串数为止

因此字符串总数= |∑|^0 + |∑|^1 +…|∑|^n = (|∑|^n−1)/(|∑|−1) (通过几何级数)，它是一个有限数，因为n是有限的。

然而，语言是无限的。因此，这与我们的假设相矛盾。