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.

Improve this question
$\endgroup$
4
  • 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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.