Question

L = {strings with the no. of a = twice no. of g where |a| >= 0} for ∑ = {a, c, g}

-Is L a context-free language? (proof)

-Does acgcca ꞓ L ? Use the sentential form derivation approach.

Answer 1

A language is said to be context free language if it has a context free grammar for the given language.

CFG should have one nonterminal on the left habd side of production.

L = {strings with the no. of a = twice no. of g where |a| >= 0} for ∑ = {a, c, g}

L={e,c,cc,ccc,aacg,aaaagg,aacg,........}

so the string belongs to the language

acgcca ꞓ L(true).