[Solved]: Can this language be defined by a Context Free Grammer?

Problem Detail: 

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 ?

Asked By : Zulqurnain jutt

Answered By : Bergi

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43986

3.2K people like this

 Download Related Notes/Documents