Is it possible to prove that L is a regular language?

Let L = {a^f(m) | m >= 1 } where f: Z^+ -> Z^+ is monotone increasing and complies that for all element n in Z^+ there is an m开发者_运维知识库 belonging to Z^+ such that f(m+1) - f(m) >= n.

Is it possible to prove that L is a regular language?

Let f(x) = 2^x. For any positive n, f(n+1) - f(n) >= n.

L = {a^f(m)} is not regular. Consider the strings a^(2^x + 1). After an FA processes such a string, the smallest string which leads to an accepting state is a^(2^x - 1), having length 2^x - 1. Therefore, a separate state will be needed for every value of x. Since there are infinitely many values of x (positive integers), no FA exists to recognize L; ergo, L is not a regular language.