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

Problem Detail: 

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?

Asked By : Alex

Answered By : godfatherofpolka

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 \not\in L$, which contradicts our initial assumption that $L$ is regular, hence $L$ is not regular.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23290

 Ask a Question

 Download Related Notes/Documents