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?

  • 1
    $\begingroup$ This is a dump of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Mar 31 '14 at 11:40
  • $\begingroup$ Alex actually you didn't understand why $L = \{ a^p \mid p \text{ is prime} \}$ is not regular.. I suggest you to read what is called regular language, pumping lemma proof for first language then think about your next language. $\endgroup$ – Grijesh Chauhan Mar 31 '14 at 18:46

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.

| cite | improve this answer | |
  • $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$ – Raphael Mar 31 '14 at 11:40
  • 1
    $\begingroup$ @Raphael Sorry, it's my first day here, I will have a look at your link. $\endgroup$ – godfatherofpolka Mar 31 '14 at 11:48
  • 2
    $\begingroup$ No worries, our conventions are not immediately apparent and we know that. Thanks for taking the time to answer and reading up on policy, and welcome to Computer Science! $\endgroup$ – Raphael Mar 31 '14 at 11:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.