# Show that $L = \{a^p b^q \mid p, q \in \mathbb{N}^0 \setminus \mathbb{P}\}$ is not regular

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?

• The command is \setminus, not \setdiff :) – Cameron Williams May 18 '16 at 3:20
• 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. – Aravind May 18 '16 at 4:28
• Right. I had it in my head that the PL held true for all decomposistions of strings of sufficient length. Thanks for correcting me. – Nick Broderick May 18 '16 at 11:26

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.
• 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. – Nick Broderick May 18 '16 at 11:33
• 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. – J.-E. Pin May 18 '16 at 15:57