Context Free Grammar for L= { a^n b^m c^m d^2n }, where n and m are >= 0

Question

Question: Design Context Free Grammar for L= { a^n b^m c^m d^2n }, where n and m are >= 0

This is how i made it:

s -> ABC ( This is the start symbol generating the entire string. )
A -> aA | null ( Generates the a^n part )
b -> bBc | null ( Generates the b^m c^m part )
c -> ddC| null( Generates the d^2n part )

I've solved this question, Can anyone tell me is this correct CFG for above question?

Answer 1

The given language is in fact a context-free language. So, one can provide a context-free grammar (CFG) for it. However, the above-described grammar is not a correct one for the given language. The variables A and C work independently. Therefore, this grammar does not guarantee that the number of d's is twice the number of a's. The following grammar is OK:

S -> aSdd | T
T -> bTc | epsilon

First, two d's are generated for each terminal a. When the variable S finishes generating the beginning and end of the string, the variable T starts making the middle part.