I was solving one of my practice questions, defining a language with Context Free Grammar Productions , but I am stuck on one question , Here are my attempt:

Question: $L = \{a^n b^m c^p \mid n = m + p + 2\}$

My Attempt: 

S -> aaBC

B -> aBb | ^

C -> ?  (Now how can i increase length of `a` Terminal by C as i increased from B)

Is this language not context free / impossible ?

  • $\begingroup$ Welcome to SE Computer Science. WHat do you call an "impossible" language? Why do you use the tag automata when there is no automata issue in your question? $\endgroup$
    – babou
    Jun 28 '15 at 7:25
  • 1
    $\begingroup$ You may be interested in our reference questions. $\endgroup$
    – Raphael
    Jun 28 '15 at 9:48

You'll need to "wrap" the Bs in the Cs:

S -> aaC
C -> aCc | B
B -> aBb | ɛ

With that, we have

$L(B) = a^m b^m$,

$L(C) = a^p \cdot L(B) \cdot c^p = a^p a^m b^m c^p$ and

$L(S) = a^2 \cdot L(C) = a^2 a^p a^m b^m c^p = a^{m+p+2} b^m c^p$.


As noted by Raphael in one of the comments an appraoch to this question is given in one of the reference questions: "How to prove that a language is context-free?".

Try to write the language in such a way that the nesting structure can be handled by a CFG.

$L=\{a^nb^mc^p\mid n=m+p+2 \} = \{a^{m+p+2}b^mc^p\mid m,p\ge 0 \}$

This does not work, so reorder:

$L=\{a^{p+m+2}b^mc^p\mid m,p\ge 0 \} = \{a^pa^ma^2 b^mc^p\mid m,p\ge 0 \} $.

Then apply nesting, peeling the layers of the string like an onion.

$S\to aSc$, $S\to T$, $T\to aTb$, $T\to a^2$.

  • $\begingroup$ this method cannot be used when i have condition like n = m + p - 2 $\endgroup$ Jun 29 '15 at 7:40

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.