# Proving $L=\{a^{n+3}b^{2m}|n≠m\}$ is not context free using the pumping lemma

Say if the language is context-free or not. If it is, write a context-free grammar, if not, demonstrate using the pumping lemma. $L=\{a^{n+3}b^{2m}|n≠m\}$

I have seen a lot of examples using the context-free pumping lemma, but none of them have the requirement of n≠m. I can't think of any demonstration for this one. If anybody has any idea, it would be great to hear it. Thanks.

## 1 Answer

Perhaps it is context-free? If it is, you intuitively need to have two derivation paths, one for $n > 2m-3$ and one for $n < 2m-3$. Can you figure each one out?

• I can't think of any PDA which could recognise the language (therefore I assumed it's not CF). How can I put in a grammar such a restriction? I mean on a Turing machine, this can be done, but on a PDA... – Alina Voicu Sep 4 '15 at 9:23
• @AlinaVoicu: Well you should first try to find a CFG for $\{ a^m b^n : m > n \}$, before trying to generalize to the kind that you want. – user21820 Sep 4 '15 at 11:44
• Ok. This is what I have for $L=\{a^mb^n, n≠m \}$. For m>n: S->aA|a, A-> aAb|aA|ab|a. For m<n: S-> Ab|b, A->aAb|Ab|ab|b. Is it correct? – Alina Voicu Sep 4 '15 at 12:01
• @AlinaVoicu: Yes so you can clearly combine them together.. you can in fact simplify because all that matters (say for $m>n$) is that you produce at least one 'a' first and thereafter no less 'a's than 'b's, so we could use $S \to aA$; $A \to ε|aAb|aA$. It's similar to get $n > 2m-3$. – user21820 Sep 4 '15 at 13:16
• I was wondering....the language can be also written $a^3a^nb^mb^m$. Can't I simply add to the grammar I already created so it has the 3 a's in front and double the b's added? Something like: For n>m: $S→aaaA$ ; $A→ε|aaAbb|aA$? Doest it make any sense? – Alina Voicu Sep 4 '15 at 14:23