# Can this language be defined by a Context Free Grammer?

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 ?

• 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? – babou Jun 28 '15 at 7:25
• You may be interested in our reference questions. – 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$.

• this method cannot be used when i have condition like n = m + p - 2 – Zulqurnain Jutt Jun 29 '15 at 7:40