5
$\begingroup$

$L = \{a^n b^m | m \not= n^2 \}$ I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck.

Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ and $b$ symbols in them. Otherwise pumping would generate strings not of the form $a^i b^j$.

Hence both $v$ and $y$ must consist only of one kind of symbol each. Beyond this I wonder what string in $L$ has to be chosen in order to pump and obtain something of the form $a^n b^{n^2}$.

Alternative idea : Assuming that $L$ is context-free, then I must have a PDA accepting it by final state. Can I say that this PDA can be adjusted* to accept $L'$ i.e., all $a^n b^{n^2}$ ? However I know that $L'$ is not a CFL. Hence, contradiction ?

*Adjusted = Make the non-final state on reading $a^n b^{n^2}$ as final and the rest as all non-final.

$\endgroup$
  • $\begingroup$ Have a look at our reference question for more techniques. $\endgroup$ – Raphael Apr 7 '13 at 19:04
  • $\begingroup$ Is this not a context free language? Since when $m=n$ this language is Context Free $\endgroup$ – user5507 Apr 10 '13 at 2:35
2
$\begingroup$

Examining this answer mentioned by Raphael,

I don't believe the pumping lemma could help you with this language. It seems you can always choose the part to pump so that you will "miss" the condition that $m=n^2$.

I also believe the same difficulty will be there if you try to use Ogden's Lemma, which generalize the pumping lemma to deal with such problematic questions, (marking $N$ places will reduce to pumping the marked substring.)

However, the method using Parikh's Theorem, should work and is not very difficult for this case, since $\Psi(L) = \{ (n,m) \mid m\ne n^2\}$. You are left to show that it is not a finite union of "linear" sets. Not too easy, but should be doable.

$\endgroup$
2
$\begingroup$

Your first approach is not very clear. What are $n$ and $m$? You have to fix a word in order to use the Pumping lemma; please see our reference question for how it's done.

Your second approach is fundamentally flawed as CFL is not closed against complement, i.e. your PDA construction does not work. Also, note that $L^c$ does not only contain words of the form $a^nb^{n^2}$, but also all that do not match $a^*b^*$.

Towards showing that $L$ is not context-free, note that $\mathrm{CFL} \cap \mathcal{L}(a^* b^*)$ is closed against complement (see here). Therefore, if $L$ was context-free so would be

$\qquad L' = \{a^n b^m \mid m = n^2\}$.

It is easy to show that $L'$ is not context-free by using the Pumping lemma.

$\endgroup$
  • $\begingroup$ Hey, thanks for pointing it out. I edited the question. I meant, we could adjust the PDA a little bit to make it accept a language that is not context-free. As for the first approach, my problem is with that exactly. What should be $m$ and $n$? All I have done is stating some generic statements that holds good for any $m$ and $n$. $\endgroup$ – Enigman Apr 8 '13 at 15:55
  • $\begingroup$ @Enigman Please work through the examples in the reference question, that should answer your question. Basically, you are approaching the Pumping lemma in a completely wrong way. $\endgroup$ – Raphael Apr 8 '13 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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