I am interested to know whether that language $$L = \{ a^pb^q \mid p, q \text{ are prime} \}$$ is regular. How do you prove that it is not regular?
Is the language $\{ a^pb^q \mid p, q \text{ are prime} \}$ regular?
formal languages;regular languages
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_theoremTo 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$y$ is not the empty string,$xy$ has at most length $l$,$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 \not\in L$, which contradicts our initial assumption that $L$ is regular, hence $L$ is not regular.