Are {a^n | n >= 0} and {a^p | p = prime number} not regular?

Question

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?

Solution

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.

Comments

[Benjy Kessler]

This might be more relevant to cs.stackexchange.com.

[harold]

The first is regular (proof: well it's a*), the second is not. You can show that you can pump a number of times that guarantees there is a divisor.

[T.C.]

Really? N=7, s=2, N+3s=13, which is prime. The obvious choice for m is N+1, yielding a final length of (1+s)N which is self-evidently nonprime for any positive integer s.