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 '13 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 '13 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 '13 at 11:44

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$ – reinierpost Sep 14 '13 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 '13 at 14:03
  • $\begingroup$ I think Hendrik Jan is correct and you can use the pumping lemma to prove it. $\endgroup$ – reinierpost Sep 14 '13 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 '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 $$

  • $\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 '13 at 13:58
  • $\begingroup$ thanks @Huynh for pointing this out I will try to correct that.... $\endgroup$ – p.j Sep 14 '13 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 '13 at 8:09

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.