context-free-grammardfaformal-languagescontext-free-languagepumping-lemma

CFL Pumping Lemma L = {a^n b^m c^k d^k | n>m}

I have some troubles solving this exercise with context free pumping lemma. Can someone help?

Solution

  • This language can be shown not to be regular using the pumping lemma for regular languages. It is context free and this is a grammar for it:

    S -> LR
L -> a | aL | aLb
R -> e | cRd

    Basically, recognize the a/b part is totally separate from the c/d part and concatenate grammars for each of the two.