1. Star Operator and Grammer

I am not sure if this is where I can get help for it but I thought its worth a try.

Prove that L = {a^n: n is a prime number} is not regular

I was looking through the solution to it but don't understand it at all, could anyone help explain how to solve it?

Thanks

2. Originally Posted by taurus
I am not sure if this is where I can get help for it but I thought its worth a try.

Prove that L = {a^n: n is a prime number} is not regular

I was looking through the solution to it but don't understand it at all, could anyone help explain how to solve it?

Thanks
I don't have much experience with this but I believe the pumping lemma directly applies. Based on the informal definition, if L is regular then by pumping lemma there exist integers m and n such that n > 1 and m > 0 and n + km is prime for any positive integer k, which can be disproven by letting k = n.

3. n > 1 and m > 0 and n + km is prime for any positive integer k, which can be disproven by letting k = n

Thats where I lost it, what is m? and why did you say n + km?

4. Originally Posted by taurus
n > 1 and m > 0 and n + km is prime for any positive integer k, which can be disproven by letting k = n

Thats where I lost it, what is m? and why did you say n + km?
So I was going based off of the informal definition, assuming "between" means there are non-empty strings on either side, and that the pumped substring had to appear at least once. Since this is not the case, a better statement would be

there exist integers m and n such that $n \ge 0$ and m > 0 and n + km is prime for any non-negative integer k...

So we have word of length p, call it w = xyz with variables named according to the pumping lemma @ Wikipedia. x and z are allowed to be empty; call their combined length n. The length of y must be nonzero, call it m. We can repeat y as many times as we want; if we repeat k times, the length of the word is n + km, and this word must be in the language by the lemma. Thus n + km is prime for all non-negative integers k, which we will prove is false. Not having n > 1 makes it slightly more work but not much.

If n < 2 let k = 0, which gives a contradiction since neither 0 nor 1 is prime.

If n > 1 let k = n, then n + km = n + nm = n(1 + m) which is greater than n and divisible by n, thus not prime.

5. AHH ok makes much more sense, I would just be confused on the km, I think I would have done m^k

6. Originally Posted by taurus
AHH ok makes much more sense, I would just be confused on the km, I think I would have done m^k
Ah, it's just that k, m, and n are integers, not words.

7. Suppose there existed a finite automaton that recognizes exactly that language, let $N$ be the number of distinct states in it.

Consider $\epsilon=a^0,a^1,...,a^N$ , 2 of these must be in the same state (by pidgeonhole principle), that is $a^i$ is in the same state as $a^j$ for some $0\leq i (*).

Now pick an arbitrary prime $p\geq i$ , we have that since $a^p$ is accepted, then so is $a^{p + j-i}$ by (*) since $a^{p-i}a^i$ and $a^{p-i}a^j$ must be on the same state. So that for the difference between 2 consecutive primes we have $\lim\sup {(p_{k+1}-p_ k)} \leq j-i$ ABSURD!

Why? Because $n!+2,...,n!+n$ are all composite, and you can picked $n$ as large as you want. - so we can alwas find a pair of prime numbers (such that there's no other prime between them) such that the difference between them is as large as you want.

Note: We could also have said that $a^{p+r\cdot (j-i)}$ are accepted for all r in $\mathbb{N}$ and pick $r=p$ to get a contradiction

In general, if you have an increasing sequence $b_k$ of non-negative integers such that $\lim\sup (b_{k+1}-b_k)=+\infty$ then the language $L=\{a^{b_k}\text{: }k\in\mathbb{N}\}$ is not regular.

So for example, this same trick applies to sequences like $b_k =k^2$ .