I'm stuck as to figuring out why $L_1$={$n^p$ | $p$ = a prime number} is not a regular language but $L_2$={$n^p$ | $p$ = a prime number bounded by some fixed number f} is. I can see that $L_2$ is a finite language so it's a regular language. But I can't seem to find a way to build a finite state machine (that is, draw a transition diagram) that would model this.
Thanks all.
On
Hint: You have given a perfectly good proof that $L_2$ is regular. To show that $L_1$ is not regular, use the Pumping Lemma.
Suppose to the contrary that the language is regular. Since there are arbitrarily large primes, there are integers $a$ and $d\gt 0$ such that all strings of length $a+kd$ are in the language. But the arithmetic sequence $(a+kd)$ contains composite numbers. For pick a $k_0$ such that $a+k_0d \gt 1$. Then $$a+k_0d + (a+k_0d)d=a+(k_0+a+k_0d)d$$ is in our arithmetic sequence. It is divisible by $a+k_0d$ and greater than $a+k_0d$, so is not prime.
On
In order to show that $L_p = \{ a^i : \text{prime}(i) \}$ is not a regular language using the pumping lemma, you must construct a string $w \in L_p$ which cannot be pumped in the manner germane to regular languages. In this case, the goal is to show that pumping some string $w \in L_p$ will generate a string the length of which is composite. Here is a relatively simple proof using the pumping lemma.
Suppose that $L_p$ is regular. Since $L_p$ is regular, there exists a $\text{DFA}$ $M$ with $k$ states such that, for every string $z \in L_p$ such that $k \leq \text{len}(z)$, $z$ can be decomposed into substrings $uvw$ such that $\text{len}(uv) \leq k$, $0 < \text{len}(v)$, and $uv^iw \in L_p$ for all $i \geq 0$.
Let $n$ be a prime number. Since $n$ is prime, the string $a^n$ is a member of $L_p$. Since $a^n$ is a member of $L_p$, $a^n$ can be decomposed into substrings $uvw$ satisfying the conditions of the pumping lemma. In particular, $uv^{n + 1}w$ must be a member of $L_p$. However, $\text{len}(uv^{n + 1}w)$ is not prime: $$ \begin{align} \text{len}(uv^{n + 1}w) & = \text{len}(uv^nvw) \\ & = \text{len}(uvw) +\text{len}(v^n) \\ & = n + n\cdot\text{len}(v) \\ & = n(1 + \text{len}(v)) \end{align} $$ Since $n(1 + \text{len}(v))$ is composite, its length is not prime. Therefore, $uv^{n + 1}w$ is not a member of $L_p$, a contradiction. Therefore, $L_p$ is not a regular language.
In order to show that the language of primes bounded by a natural number is regular, you can use the construction demonstrating that every finite language is regular. However, since you already know that every finite language is regular, there is no need to provide the construction.
$L_1=\{ n^p\quad |\quad \text{p=prime number} \}$ is not regular language ,can easily be proved by pumping lemma.
Let $k$ be the pumping lemma constant.
and the string $\alpha \beta \gamma$ as $\epsilon$ , $a^p$ and $\epsilon$ respectively such that $\alpha \beta \gamma \in L_1$ and $|\beta|\geq k$.
So ,if we decompose $\beta$ into $\beta _1(|\beta_1|=r),\beta _2(|\beta_2|=t),\beta _3(|\beta_3|=s)$ such that $|\beta_2| \neq \phi $,$|\beta_2| \leq k$.
Then choose $i=p+1$ ,we will get $|\alpha \beta_1 \beta_2^i\beta_3\gamma|=p(1+t)$ which is a composite.
But if we bound the prime number by $f$ then enumerate all $p<f$ and build a NFA that first guesses the prime then take that many steps to reach the final state.