Are {a^n | n >= 0} and {a^p | p = prime number} not regular?
In a CS course, I have the following examples: {a^n | n >= 0} and {a^p | p = prime number}
Are those languages regular or not? Is there anyone who can make a pumping lemma contradiction?
Answer
As harold said. This example
a^n|n>=0
is a regular language, it´s a*.
The second example
{a^p | p = prime number}
As pumping lemma says, N = p -> our word will be a^N. So, by definition |uv|< N we can chose u=a^p (p>=0) and v=a^s (s>=1). Rest of the world will be our w=a^(N-p-s). Definition says, that uv^mw (m>=0) must be in language. We can chose m=N+1.
u*v^(N+1)w = a^pa^(s*(N+1))*a^N-p-s = a^N(S+1)
There is conflict, becouse a^N(S+1) is not a prime (becouse divider is certainly S+1), so this language is not regular.