1
$\begingroup$

Consider the language $L = \{0^p \mid p \text{ is a composite number}\}$.

I know that this is not a regular language. I have thought that to prove this language is not regular take the complement (prime numbers) which must be regular, but its complement has prime numbers and 0 and 1 occurrences of 0's.

Could anybody give me a hint to prove without taking complement?

$\endgroup$

marked as duplicate by Yuval Filmus, Evil, David Richerby, Rick Decker, Juho Feb 15 '17 at 20:18

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Your argument works, using closure properties of the regular languages; in particular adding or removing a finite number of words doesn't alter the regularity status of a language. $\endgroup$ – Yuval Filmus Feb 8 '17 at 14:25
  • $\begingroup$ Why do you want to do this without taking the complement? It seems like you have a perfectly good proof of the claim already. If this is an exercise, we're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Feb 8 '17 at 17:06
  • $\begingroup$ @YuvalFilmus I don't think this is really a duplicate of the question you've suggested. This question asks for a proof of non-regularity using a specific technique. The other question asks for a proof that the language isn't context-free. I guess your pumping-lemma proof that it's not context-free is also a proof that it's not regular that doesn't use the complement, but I don't think that's really what this question is looking for. (And your proof that the language isn't context-free via non-regularity and Parikh uses complementation to prove non-regularity). $\endgroup$ – David Richerby Feb 9 '17 at 12:53
1
$\begingroup$

The Pumping Lemma will give you a way to generate strings in the language whose lengths are in an arithmetic progression. If you pick the initial string right, you should be able to apply Dirichlet's (?) Theorem that arithmetic progressions having certain properties necessarily include infinitely many primes.

$\endgroup$
  • $\begingroup$ You can find this very argument in the answer to the question mentioned in the comments. $\endgroup$ – Yuval Filmus Feb 8 '17 at 19:33
1
$\begingroup$

It can also be proved by taking the complement. This doesn't answer your question as per the last sentence, but shows how you could extend your arguments in the second paragraph.

Let $$L_1=\{0^p| p\text{ is a prime}\}$$ Then, we have the complement of $L$ to be, $$\bar{L}=L_1\cup\{\epsilon,0\}$$ where $\epsilon$ denotes the empty string.

$L\cup\bar{L}=\Sigma^*$, where $\Sigma=\{0\}$, the alphabet of the language. Also, $L$,$L_1$, and $\{\epsilon,0\}$ are all pairwise disjoint.

Thus,

$$\begin{align}L_1&=\Sigma^* -(L\cup\{\epsilon,0\})\\ &=\Sigma^*\cap \overline{L\cup\{\epsilon,0\}} \end{align}\tag1$$

Suppose $L$ was regular. We know that $\{\epsilon,0\}$ is regular as the number of strings in the language is finite. By the closure under union, we must have $L\cup\{\epsilon,0\}$ to be regular. Again, by closure under complement, we must have $\overline{L\cup\{\epsilon,0\}}$ to be regular. As $\Sigma^*$, the set of all strings is regular, by closure under intersection, $\Sigma^*\cap \overline{L\cup\{\epsilon,0\}}$ must be regular. From $(1)$, this means that $L_1$ must be regular.

Using the pumping lemma, as suggested by you, it can be shown that $L_1$ is not regular, leading to a contradiction. Thus, the assumption that $L$ is regular is incorrect, $L$ is not a regular language.

$\endgroup$

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