[Solved]: Is the language ${ a^pb^q mid p, q text{ are prime} }$ regular?

This language is not regular, the easiest way to see this is to use the Pumping Lemma, see http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages Alternatively, you could also use the Myhill-Nerode theorem, see http://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem To give you some more details, assume (towards a contradiction) that $$ L = { a^pb^q mid p,q text{ are prime} } $$ was regular. By the Pumping Lemma, there is an integer $l geq 1$ such that every word $w in L$ of length at least $l$ can be written as $w=xyz$ with

1. $y$ is not the empty string,
2. $xy$ has at most length $l$,
3. $xy^iz in L$ for every $i geq 0$.

Now we can pick $w$ as $a^2b^q in L$ for some prime $q geq l$. This word meets the conditions of the Pumping Lemma. Without loss of generality we can assume that $xy=a^2b^k$ for some $k geq 1$ (the case for $xy=a$ or $xy=aa$ is even simpler). Now, either $y=a^jb^k$ for some $j geq 1$ or $y=b^k$. But in both cases, we immediately see that we can choose $i geq 0$ such that $xy^iz notin L$, which contradicts our initial assumption that $L$ is regular, hence $L$ is not regular.