Regular expression describe the same set of string as Grammar

Question

Consider the following Grammar

S -> Ax/By

A->By/Cw

B->x/Bw

which of the regular expression describe the same set of strings as the grammar?

 

The option are:

(a) xw* y + xw* yx +ywx

(b) xwy + xw* xy +ywx

(c) xw* y + xw X yx +ywx

(d) xw xy + xww* y +ywx

Comments

for this particular problem, none of the options match, but i think there is a production missing as evident from: https://www.tcyonline.com/discuss/que/3694/consider-the-following-grammar-s-gt-ax-bya-gt-by-cwb-gt-x-bwc-gt-ywhich-o

---

@Aishik, I too also feel. Tat u r right. Since in d regular expression there is a null in d strings given. But none of d above productions carry a NULL value. All d more from d string which are  given in  d options, doesn't seem to be matching with d Productions. :)

---

Is there any production as

C $\rightarrow$y

I think I should be

---

Exactly. without C->y none of the options are matching.

Answer 1

Grammar is

S$\rightarrow$Ax|By

A$\rightarrow$ By|Cw

B$\rightarrow$ x|Bw

C$\rightarrow$ y

Now observe that what strings these productions are generating

C$\rightarrow$ y is generating only y.

B$\rightarrow$ x|Bw is generating x, xw, xww, xwww, ... That is xw*.

A$\rightarrow$ By|Cw is generating xw*y+yw.

S$\rightarrow$ Ax|By is generating (xw*y+yw)x+xw*y .

That is regular expression for given grammar.

Comments

@Praveen Sir,Thank u for d explaination.Explained in detailed manner.:)