Here is a question that I encountered in one of my exams:

Find one context-free grammar that recognizes the language: $\qquad L = \{a^n(b^mc^m)^pd^n \mid m, n, p \geq 0\} $

Can you find such a grammar? I even doubt its existence, but I have not been able to prove that.

  • $\begingroup$ What have you tried? In particular, have you tried disproving the claim? $\endgroup$
    – Raphael
    Sep 16, 2013 at 8:05
  • $\begingroup$ @Raphael: I tried using the "pumping" lemma. Do you want to see the proof? (I haven't verify that it's correct though!) $\endgroup$
    – Huynh
    Sep 17, 2013 at 9:03
  • $\begingroup$ Now it's too late as you already have answers. Make sure you make your attempts prior to posting next time you have a question! (Beware falling into the "check-my-answer" trap, though; see here and here.) $\endgroup$
    – Raphael
    Sep 17, 2013 at 11:44

2 Answers 2


No, this language is not context-free. This is because the language requires to iterate $b^mc^m$ with the same number $m$ each time. Even if we restrict to $n=0$ and $p=2$ then the resulting language $\{b^mc^mb^mc^m \mid m\ge 0\}$ is easily recognized as non-context-free. Formally this restriction is obtained by intersecting with a regular language, a known closure property of context-free languages. To prove a language formally non-context-free one might use the pumping lemma discussed elsewhere in this forum.

Perhaps that is a mistake in its specification. If for each iteration the number $m$ can be different, the resulting language is context-free. That language would be $L_1 = \{ a^n w d^n \mid n\ge 0, w\in \{\; b^mc^m \mid m\ge 0\}^* \;\}$. As an example, $bbbcccbc$ is an element of $L_1$, but not of $L$.

How to find a grammar (for $L_1$)? Observe the nesting structure. Context-free grammars are good in nesting, and iteration. For instance the part $\{\; b^mc^m \mid m\ge 0\}^*$ is generated by $T\to AT, T\to A, A\to bAc, A\to\lambda$, starting with $T$. Now add a matching number of $a$'s and $d$'s on both sides by nesting: $S \to aSd, S\to T$.

  • $\begingroup$ Why would requiring the same numbers of $b$s and $c$s be a problem? $\endgroup$ Sep 14, 2013 at 13:58
  • $\begingroup$ @Hendrick: Could you please provide a formal proof or some directions (lemma/theorem)? I mainly read "Discrete Mathematics and Its Application", but it does not seem to be "deep" enough about this. $\endgroup$
    – Huynh
    Sep 14, 2013 at 14:03
  • $\begingroup$ I think Hendrik Jan is correct and you can use the pumping lemma to prove it. $\endgroup$ Sep 14, 2013 at 14:07
  • $\begingroup$ @Huynh Formal proof of the first part of the argument. Suppose that $L$ is context-free. Since the intersection of a context-free language with a regular language is context-free, then $L \cap b^*c^*b^*c^* = \{b^mc^mb^mc^m \mid m \geqslant 0 \}$ should be context-free. $\endgroup$
    – J.-E. Pin
    Sep 15, 2013 at 5:16

As @Hendrik mentioned, if m is not to be remembered ie it can be different than I think following grammar will work .. $$ A \rightarrow a A D | a B D | \lambda $$

$$ B \rightarrow b B c | b B c P|P $$ $$ P\rightarrow bPc|bPcB|\lambda $$ $$ D \rightarrow d $$

  • $\begingroup$ I think this is not correct though. For example: A->aAD->aD->a, and the number of a's is not the same number of d'. $\endgroup$
    – Huynh
    Sep 14, 2013 at 13:58
  • $\begingroup$ thanks @Huynh for pointing this out I will try to correct that.... $\endgroup$
    – Parag
    Sep 14, 2013 at 15:26
  • $\begingroup$ This answer could be improved if you added some ideas to it. As it stands, it solves the specific question (if that) but does not help the OP in solving similar problems. $\endgroup$
    – Raphael
    Sep 16, 2013 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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