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

198 Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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.