Full disclosure: this is a homework question, so I'm only looking for a kick in the right direction.

The original question notes that $\{a^p \mid \ p \in \mathbb{P}\}$ is not regular and that the derivation should be possible using "the properties of regular languages". I take this to mean the closure properties - except the homomorphism properties, which my class has not covered - and the Pumping Lemma.

If this can be done using just the closure properties it must involve finding a regular language $R$ and a non-regular language $L'$ for which $R \circ L = L'$, where $\circ$ is one of union, intersection, set difference or concatenation. But I can't find any useful choices on inspection. If I'm resigned to using the Pumping Lemma to arrive at the result by contradiction, I fail to see how any string in $L$ could be pumped to achieve this, as knowing how much the string needs to be pumped to force one of $p$ or $q$ to be prime - necessary to force the string outside of $L$ - seems impossible to me.

Edit: minutes after finishing the question I just thought of a strategy to pump the string. Assume $L$ is regular, and that $n$ is the pumping length. Take $\sigma = a^pb^q$, where $p + q = n$. Certainly, the length $\sigma$ matches the pumping length, and so can be decomposed as $\sigma = \alpha \beta \gamma$, with $\alpha = a^{p-1}$, $\beta = ab$ and $\gamma = b^{q-1}$. Then for some $m > 1$, $\alpha \beta^m \gamma \notin L$, otherwise the sequence $(q+1, q+2, ...)$ would necessarily be comprised only of composite numbers, which is impossible.

Is this a valid argument?

  • $\begingroup$ The command is \setminus, not \setdiff :) $\endgroup$ – Cameron Williams May 18 '16 at 3:20
  • $\begingroup$ You can't choose $\alpha$, $\beta$, $\gamma$; you have to show that for any values of these, the lengths of $\alpha {\beta}^m \gamma$ are not always composite. $\endgroup$ – Aravind May 18 '16 at 4:28
  • $\begingroup$ Right. I had it in my head that the PL held true for all decomposistions of strings of sufficient length. Thanks for correcting me. $\endgroup$ – Nick Broderick May 18 '16 at 11:26

Your question can indeed be solved in a short way using the closure propeties of regular languages. Since you just ask for a kick in the right direction, I just give you a hint for the first (and more important) step. I will give you more details only if needed.

Hint. If $L$ is regular, then for each regular language $K$, $L \cap K$ is also regular. Try to find a suitable regular language $K$ which invalidates this conclusion.

  • $\begingroup$ I think I see it now that you've helped me focus on the operation that matters. Take $K = \{a\}^*$, which is certainly regular. Then $K \setminus (K \cap L) = \{a^p \mid p \in \mathbb{P} \}$ is regular whenever $L$ is. But this language is indeed not regular, as given in the question. Hence, $L$ is not regular BYOC. $\endgroup$ – Nick Broderick May 18 '16 at 11:33
  • $\begingroup$ I was not sure about your notation $\mathbb{N}^0$, but if this set includes $0$, which is not a prime, then you got exactly the solution I was thinking of. $\endgroup$ – J.-E. Pin May 18 '16 at 15:57

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.