UGC NET CSE | December 2015 | Part 3 | Question: 26

Question

The context free grammar given by
$S \rightarrow XYX$
$X \rightarrow aX \mid bX \mid \lambda$
$Y \rightarrow bbb$
generates the language which is defined by regular expression:

• A. $(a+b)^*bbb$
• B. $abbb(a+b)^*$
• C. $(a+b)^*(bbb)(a+b)^*$
• D. $(a+b)(bbb)(a+b)^*$

Comments

Its simple All string containing bbb as sub string .

(a+b)*(bbb)(a+b)*

Answer 1

looking at  X-> aX | bX | eps

we see that X  is generating (a+b)*

now simply replacing X by (a+b)*

and Y by bbb  in S-> XYX

we get (a+b)*bbb(a+b)*  option c