# 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? 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 Jun 29 '15 at 7:40