2
$\begingroup$

I am struggling to prove the following question.

$L_1 = \{a^n: n \text{ is a product of exactly two primes}\}$

I feel like the language is not regular but I am having trouble proving it. I tried using pumping lemma but got stuck at the end. Here's how I did it:

Assume that the language is regular and $m$ is a constant of Pumping Lemma. Now let $w = a^M$ where $M > m$ and $M$ is a co-prime number. Clearly $w$ is in the language and $|w| > m$.

Now let $y=a^j$ where $j$ is between $1$ and $m$, with $|xy| \leq m$ and $|y| \geq 1$.

This is where I am getting stuck. I feel like we should pump up but I don't know by "how much". Also, I feel like I have to know what is the next co-prime number after $M$, but can't figure it out.

$\endgroup$
  • 2
    $\begingroup$ Hint: convert to the language of primes by intersecting with the language of even-length strings and applying an inverse homomorphism. $\endgroup$ – Yuval Filmus Oct 12 at 17:45
3
$\begingroup$

Just pump up $(M+1)$ $y$'s. Now you get $xy^{M+1}z=a^{(M+1)j+M-j}=a^{M(j+1)}$. Since $M$ is a product of two primes, $M(j+1)$ is a product of at least 3 primes, so $a^{M(j+1)}\notin L_1$, which proves $L_1$ is not regular by the pumping lemma.

$\endgroup$
2
$\begingroup$

Here is yet another proof. It is known that the number of integers at most $n$ which are the product of two primes is $o(n)$, see for example this answer, which gives the asymptotic $\frac{n\log\log n}{\log n}$. This means that your language is infinite yet has vanishing asymptotic density. This is impossible for a regular unary language.

$\endgroup$
  • $\begingroup$ Regular unary infinite language. I would think it applies to all regular infinite languages, because such a language must have a finite state machine with some fixed length cycle, and that cycle produces density > 0. $\endgroup$ – gnasher729 Oct 15 at 12:21
  • $\begingroup$ @gnasher729 Consider $1^*$ over $\{0,1\}$. Your claim becomes correct if you only consider the lengths of words in a language. $\endgroup$ – Yuval Filmus Oct 15 at 12:34
1
$\begingroup$

There is an alternative to the “pumping” lemma which I find easier: After each possible input, determine the set of continuations that would complete a string of the language. You can use each of those sets as a state in the finite state machine for the language, so if there is a finite number of those sets then the language is regular- if there are infinitely many different sets, the language is irregular.

In your case, after processing k symbols, a further pq-k symbols for primes p, q gives a string in the language. We’ll need some statement about primes. One statement is: The gaps between primes are arbitrarily long. Let p, q be consecutive primes with a larger gap q-p than any previous gap. After processing 2p symbols, the smallest even number of symbols to give a product of two primes is 2(q-p). Therefore, after processing 2p symbols you are in a different state than after processing 2p’ symbols for any prime p’ < p.

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