# Why isn't this a regular language?

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.

-
From the start state go along a path in p steps to a final state; now do this for all p. – i. m. soloveichik Aug 11 '12 at 4:12
See over here for a couple of techniques that can be useful for you. – Raphael Aug 11 '12 at 17:50
Is this how to draw the transition diagram for the finite state automaton (I mean L2)? I'm still not understanding how to do this....since the value of f isn't given (just that it's finite), how can I show this? – pauliwago Aug 12 '12 at 0:58

$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.

-
Could you please elaborate on the NFA part? I'm not getting it. How can I draw a NFA that guesses the prime number? – pauliwago Aug 12 '12 at 1:01
@pauliwago NFA means Non Deterministic Finite Automata, it has the power to be in several states at once which is also expressed as a ability to "guess". So lets say $f=10$,so $L_1=\{n^2,n^3,n^5,n^7\}$ then from the start state we will draw $4$ branches with $2,3,5,7$ states with last state as final state.So if $n^k$ is the input string so NFA will explore all the possibilities and if $k$ is prime it will be in final state otherwise it will be in nonfinal state or either get stuck. – Saurabh Aug 13 '12 at 17:33

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.

-
Why $a+(k_0+a+k_0d)d$ is divisible by $a+k_0d$ ? – Belgi Aug 11 '12 at 4:19
You are looking at the right-hand side, where it is not obvious. But it is obvious if you look at the left-hand side. – André Nicolas Aug 11 '12 at 4:20

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.

-
Thanks for your answer. I'm trying to figure out how to draw the NFA for L2 and am lost. If the value of f was given, I could do it, but all that's given is that it's defined... – pauliwago Aug 12 '12 at 1:04
Also for your proof for L1, how do you know after you "pump" 1, it's a composite number? That is, how do you know $n$(1+len($v$)) is not prime? – pauliwago Aug 12 '12 at 1:24
@pauliwago: I know this is 3 years late, but for anyone else looking at this, you know $n(1+len(v))$ is not prime because it's decomposed into 2 factors right there: $n$ and $1+len(v)$. – user124384 Oct 14 '15 at 2:55

Constructing DFA for l2: each value of f will result into a new language. And each language has its own DFA.

So, for a given value f, we can build a DFA with f states and mark all states corresponding to prime numbers as final state.

please correct me, if I'm wrong.

-