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.


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?

  • $\begingroup$ 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... $\endgroup$ – Alina Voicu Sep 4 '15 at 9:23
  • $\begingroup$ @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. $\endgroup$ – user21820 Sep 4 '15 at 11:44
  • $\begingroup$ 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? $\endgroup$ – Alina Voicu Sep 4 '15 at 12:01
  • $\begingroup$ @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$. $\endgroup$ – user21820 Sep 4 '15 at 13:16
  • $\begingroup$ 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? $\endgroup$ – Alina Voicu Sep 4 '15 at 14:23

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.