geeks mock 2017 #56

Question

Which of the following statements is correct about context sensitive grammar?
I) In a context sensitive grammar, ε can’t be the right hand side of any production

II) In a context sensitive grammar, number of grammar symbols on the left hand side of a production can’t be greater than the number of grammar symbols on the right hand side

III) In a context sensitive grammar, number of grammar symbols on the left hand side of a production can’t be greater than the number of terminals on the right hand side

IV) In a context sensitive grammar, number of grammar symbols on the left hand side of a production can’t be greater than the number of non-terminals on the right hand side

Isn't (II) (non contracting grammar is also CSL) and (IV) both are correct

Comments

In context free on left side only one non terminal and on right side no limitation.

what is u r doubt??

---

oh sorry I meant context sensitive typed it wrong sorry

---

@santhoshdevulapally How is 4th correct?

S —> 123 is valid. Here LHS > No. of variables in RHS.

Answer 1

For a grammar to be CSG, the length of the LHS should be less than the length of RHS. And LHS and RHS could be any combination of variables and terminals.

I) In a context sensitive grammar, ε can’t be the right hand side of any production

The production S → e is also allowed if S is the start symbol and it does not appear on the right side of any production.
So, Option A eliminated.

Source: https://www.csa.iisc.ac.in/~deepakd/atc-2016/Seminar-CSG.pdf (Page 5)

 

II) In a context sensitive grammar, number of grammar symbols on the left hand side of a production can’t be greater than the number of grammar symbols on the right hand side

Completely true! Option B is the answer

 

III) In a context sensitive grammar, number of grammar symbols on the left hand side of a production can’t be greater than the number of terminals on the right hand side

$AB -> 2CDE$ is valid. So, Option C is incorrect.

 

IV) In a context sensitive grammar, number of grammar symbols on the left hand side of a production can’t be greater than the number of non-terminals on the right hand side

$S -> 123$ is valid. So, Option D is also incorrect.

Source: https://www.csa.iisc.ac.in/~deepakd/atc-2016/Seminar-CSG.pdf (Page 8)