Question

Find the language generated by the following CFG. Express the language as a formula involving powers of the terminals and the associated conditions on the powers.

S → aa S ddd | T

T → b T cc | ε

Answer 1

Given Data-

S -> aa S ddd | T

T -> b T cc | ε

So we can write that,

S -> aa T ddd                                                         T -> ε

S -> aa ε ddd                                   

S -> aa ddd -eq.1

S -> aa T ddd T -> b T cc

S -> aa b T cc ddd T -> ε

S -> aa b cc ddd -eq.2

From eq.1 and eq.2, we can say that

L={aⁿb^mc^xd^y} where,

n >= 2,

m >= 0,

x >=2

y >= 3