-2
$\begingroup$

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?

$\endgroup$
2
  • 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, 2014 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$ Mar 31, 2014 at 18:46

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$
    – Raphael
    Mar 31, 2014 at 11:40
  • 1
    $\begingroup$ @Raphael Sorry, it's my first day here, I will have a look at your link. $\endgroup$ Mar 31, 2014 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, 2014 at 11:50

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