grammar - 是否可以证明 L 是正则语言？

Question

让L = {a^f(m) | m >= 1 }wheref: Z^+ -> Z^+是单调递增的，并遵守对于其中的所有元素n都有Z^+属于m这样Z^+的f(m+1) - f(m) >= n。

是否可以证明 L 是正则语言？

Answer 1

令 f(x) = 2^x。对于任何正数 n，f(n+1) - f(n) >= n。

L = {a^f(m)} 不规则。考虑字符串 a^(2^x + 1)。在 FA 处理这样一个字符串之后，导致接受状态的最小字符串是 a^(2^x - 1)，长度为 2^x - 1。因此，每个 x 值都需要一个单独的状态。由于 x（正整数）的值有无穷多个，因此不存在识别 L 的 FA；因此，L 不是常规语言。