-2
$\begingroup$

Let $L=\{ a^c \mid c \text{ is composite} \}$. Prove that $L$ is not regular using the pumping lemma. You can use Dirichlet's theorem, which states that if $(a,b) = 1$ then there are infinitely many prime numbers of the form $an+b$.

I am thinking about this question for a lot of days and I don't find it trivial, do you have any hints to give me about how to start the proof? please, I can see the connection between the pumping lemma and Dirichlet's theorem but I don't know how this is helping me, because the pumping lemma talks about a Periodicity, and Dirichlet's theorem talks about prime numbers and not composite so I will need to use the Complementary group

$\endgroup$
1
  • 1
    $\begingroup$ The exercise already contains instructions on how to solve it — use Dirichlet's theorem in a pumping lemma proof. $\endgroup$ May 2 at 14:32

2 Answers 2

3
$\begingroup$

Suppose towards a contradiction that $L$ is regular and let $p$ be a prime number larger than $L$'s pumping length. Since $a^{p^2} \in L$, by the pumping lemma we know that there is some $1 \le k < p$ such that $a^{ki+p^2} \in L$ for all $i \ge -1$.

Since $k$ cannot have $p$ as a prime factor, $k$ and $p^2$ must be coprime and Dirichlet's theorem guantees the existence of some $n$ such that $kn+p^2$ is prime. The contradiction follows by choosing $i=n$.

If we replace "regular" by "context-free", the proof above shows $L$ is not context-free.

$\endgroup$
2
  • $\begingroup$ thank you so much for the explenation $\endgroup$
    – Maya Cohen
    May 4 at 12:47
  • $\begingroup$ @John-l Thank you for the edit! $\endgroup$
    – Steven
    Jun 19 at 18:00
1
$\begingroup$

Let p be a prime. Since there are infinitely many primes, p is followed by n composite numbers for some n dependent on p, and then by another prime q.

After processing $a^p$ you are in a state S that is rejecting. In that state, if you process further a's, then the next n states are accepting, and the state after that is rejecting.

If the prime p is followed by n composite numbers and another prime q, and the prime p' ≠ p is followed by n' composite numbers and another prime q', and n ≠ n', then after accepting $c^p$ and $c^{p'}$ you must be in different states S and S', because in one state processing n+1 c's puts you back into a rejecting state for the first time, and in the other state you switch to a rejecting state either earlier (if n' < n) or later (if n' > n).

Gaps between primes get arbitrary large, therefore the numbers n' get arbitrary large, therefore there must be an infinite number of different state. Therefore there is no finite state machine for your language.

Sorry, no pumping lemma and no Dirichlet's theorem used.

PS. The same argument can be used for the language $c^n$ where n is / is not element of an infinite set with arbitrary large gaps between elements. For example $n = \lfloor p \log p \rfloor$ for some prime p, or $n = k!$ for some integer k.

$\endgroup$
1
  • $\begingroup$ thank you so much for the explanation! appreciate it a lot $\endgroup$
    – Maya Cohen
    May 4 at 12:47

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.