0
$\begingroup$

This question already has an answer here:

I have a question to find out that $L = \{a^m b^n\mid n>0, m - is prime \}$ is CFL or not. I know that it is not a CFL. But I don't know how to prove that. I know how to prove that $L = \{a^m\mid m - is prime \}$ is not CFL, by taking a random length for $vx$ ($uvwxy$) and prove that the length of the whole word is not prime (I manage to prove that this length is product of two factors). But with this problem I can't do this because of that $n$. At the end it results a non prime number (this product), but I have to decrease the length of $b$'s so I know nothing about that final number. Is there another method to prove that this language is not CFL or am I wrong somewhere?

$\endgroup$

marked as duplicate by D.W., André Souza Lemos, David Richerby, Luke Mathieson, Juho Jun 13 '15 at 20:23

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Your question is a basic one. Let me direct you towards our reference questions which cover multiple methods for this in detail. I suggest you work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. $\endgroup$ – D.W. Jun 12 '15 at 19:20
1
$\begingroup$

The easiest way goes as follows: if $L$ were context-free than so $L \cap a^*$ would be. Now $L' = L \cap a^* = \{ a^m : m \text{ is prime}\}$ is a unary language, so $L'$ is context-free iff it is regular iff it is eventually periodic. If it were eventually periodic then it would be either finite or have finite asymptotic density, but we know that primes are infinite and have zero asymptotic density.

You can also prove that $L'$ is not context-free using the pumping lemma. The pumping lemma shows that for some $p$, every prime $q > p$ satisfies the following: there is $1 \leq t \leq p$ such that $q + (\ell-1)t$ is prime for all $\ell$. Choosing $\ell = q+1$, we get that $q(t+1)$ has to be prime, which it isn't.

$\endgroup$

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