MADE EASY TEST SERIES

Question

Consider the following CFG:

E --> E*T/T+E/T

T --> (T*F)/F

F --> id

Which of the following strings are not generated by above CFG?

A> id+id+id

B> id∗id∗id

C> (id∗id∗id)

D> None of these

Comments

All options can be generated.

---

c ??

---

Yes. it cann't be.

---

yup, it is correct!

Answer 1

  The strings  of  Option (a) and (b)  can be generated by the given  grammar as follows:

 (a) E --> T + E => T+T+E => T+T+T => T+T+F=>T+F+F => F+F+F =>F+F+id =>F+id+id => id+id+id

 (b) E --> E * T => E*T*T => T*T*T =>F*T*T=>F*F*T => F*F*F => id *F*F=> id*id*F=> id*id*id

 but  the string (id *id *id) cant be generated as ( ) must be included into the reduction of (T*F) to T.

So the answer should be option (c).

Answer 2

because we can not generate (id * id * id) but we can ((id *id ) * id)

Answer 3

its a very common grammar.....but still just try to derive all the given strings....
1 and 2 option can be easily derived..

but if u look at option 3...we cant derive it...we can only derive((id*id)*id)....
so option should be 3rd one;;

Comments

I also solved it in the similar way and was 100 % sure that correct option is C but made easy says correct option is D.

---

they could be wrong...we cant derive the third string...;;

Answer 4

E --> E*T/T+E/T

T --> (T*F)/F

F --> id

 

whatever string we derive our derivation should start with starting symbol  E

1) id*id*id  ---->  E ------>E*T ----->E*T*T-------> T*T*T---------> id*id*id (generted)

2)id+id+id  ------>E------->T+E------->T+T+E-------->T+T+T---------->id+id+id(generted)

3)(id*id*id)   there are 2 productions by which we can generate parenthsis   "  (   ) " at begining  so analyse both of them

               i)  E------->T----------> (T*F)----------->(F*F)-------->(id*id)(not generated)

               ii)  E--------->T+E  (SINCE  WE  NEED  ALL * OPERATORS  SO  THIS IS NOT  GOING TO GIVE US ANSWER)

 

therefore answer is c)(id * id * id)