# Does this language have a context-free grammar?

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.

• What have you tried? In particular, have you tried disproving the claim?
– Raphael
Sep 16 '13 at 8:05
• @Raphael: I tried using the "pumping" lemma. Do you want to see the proof? (I haven't verify that it's correct though!) Sep 17 '13 at 9:03
• 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.)
– Raphael
Sep 17 '13 at 11:44

## 2 Answers

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$.

• Why would requiring the same numbers of $b$s and $c$s be a problem? Sep 14 '13 at 13:58
• @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. Sep 14 '13 at 14:03
• I think Hendrik Jan is correct and you can use the pumping lemma to prove it. Sep 14 '13 at 14:07
• @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. Sep 15 '13 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$$

• 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'. Sep 14 '13 at 13:58
• thanks @Huynh for pointing this out I will try to correct that.... Sep 14 '13 at 15:26
• 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.
– Raphael
Sep 16 '13 at 8:09