0
$\begingroup$

Over the alphabet $\Sigma=\{a,b\}$, we define $$L=\{a^pb^m: p\text{ is prime }, m>0\}+\{a^r:r\geq 0\}.$$

I must show that this laguage is not regular using the pumping lemma. I guess I should apply it to a word of the form $a^pb^m$, and my intuition is that I should come to the contradiction of $p$ not being prime. But I'm not very familiar with the pumping lemma, this is my first try, so I'll appreciate any hint in order to choose a word $x=a^pb^m$ with $p+m\geq n$ ($n$ from the lemma) which yields a contradiction.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Choose a word $a^pb^m$ with $p \geq n$ and $m \geq 1$ of your choice. Good luck! $\endgroup$ – Yuval Filmus Dec 31 '17 at 19:05
  • $\begingroup$ ok, then I've got $x=uvw$ with $v\neq \varepsilon$ and $|uv|\leq n$. That means that $v=a^s$ for some $1\leq s\leq n$, $|u|=a^l$ and $|w|\geq 1$ (let's say $w=a^tb^m$). Then, I use that $uv^kw\in L\forall k\in\mathbb{N}$, which is equivalent to say that $a^la^{ks}a^tb^m\in L$. Since $k$ is arbitrary, I can choose it in such a way that $l+ks+t$ is not prime. Is it fine? $\endgroup$ – Javi Dec 31 '17 at 19:32
  • 1
    $\begingroup$ Unfortunately this kind of discussion doesn't fit this platform. You should be able to tell whether your proof is valid or not. $\endgroup$ – Yuval Filmus Dec 31 '17 at 19:33
  • 1
    $\begingroup$ For "prime and pumping" arguments see here for instance Prove that the language of unary not-prime numbers satisfies the Pumping Lemma or, Prime number CFG and Pumping Lemma . There is more to find when you use the search box. $\endgroup$ – Hendrik Jan Jan 1 '18 at 13:38

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.