regular-language - Wonder是以下语言有限的

Question

在我的课堂上有一个关于以下语言是否有限的问题

{w : w 是 {a ^m b ⁿ :m+n≤k}} 的正则表达式，其中 k 是特定的自然数。

我认为它是有限的，因为语言中最多可以有(K+1)*k/2单词，但参考答案是 w 是无限的

谁能解释一下

ps：特定的正则语言只有一个正则表达式吗？

Answer 1

如果我正确地解释了您的问题，那么是的，它是无限的。我们正在寻找匹配的不同正则表达式的数量，比如 3 个字符串 'a' 和 'b'，其中所有的 'a' 首先出现。不同的正则表达式语言可以在其允许的语法上有所不同，但它们都有某种联合运算符。我们可能真的很病态，将模式中的 'a' 更改为 ('a' | 'a')，这当然会简化为 'a'，但这是一种新的编写方式。然后，通过以相同的方式继续扩展，有无数种方法可以编写该模式。