7
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ From the start state go along a path in p steps to a final state; now do this for all p. $\endgroup$ Aug 11 '12 at 4:12
  • $\begingroup$ See over here for a couple of techniques that can be useful for you. $\endgroup$
    – Raphael
    Aug 11 '12 at 17:50
  • $\begingroup$ 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? $\endgroup$
    – pauliwago
    Aug 12 '12 at 0:58
7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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... $\endgroup$
    – pauliwago
    Aug 12 '12 at 1:04
  • $\begingroup$ 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? $\endgroup$
    – pauliwago
    Aug 12 '12 at 1:24
  • $\begingroup$ @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)$. $\endgroup$
    – user124384
    Oct 14 '15 at 2:55
5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Why $a+(k_0+a+k_0d)d$ is divisible by $a+k_0d$ ? $\endgroup$
    – Belgi
    Aug 11 '12 at 4:19
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 11 '12 at 4:20
  • $\begingroup$ Why are all strings of length $a + kd$ in the language? Do you mean that there exist $a$ and $d$ such that for all $k$ all strings of the form $n^{a + kd}$ of length $a + kd$ are in the language? Why? $\endgroup$
    – dionyziz
    Feb 3 '19 at 12:57
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Could you please elaborate on the NFA part? I'm not getting it. How can I draw a NFA that guesses the prime number? $\endgroup$
    – pauliwago
    Aug 12 '12 at 1:01
  • $\begingroup$ @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. $\endgroup$
    – Saurabh
    Aug 13 '12 at 17:33
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.