GATE CSE 1995 | Question: 1.10

Question

Consider a grammar with the following productions

• $S  \rightarrow  a \alpha  b \mid b \alpha  c \mid aB$
• $S  \rightarrow \alpha  S\mid b$
• $S  \rightarrow \alpha b b\mid ab$
• $S  \alpha \rightarrow bd b\mid b$

The above grammar is:

• A. Context free
• B. Regular
• C. Context sensitive
• D. $LR(k)$

Comments

https://stackoverflow.com/questions/41752685/how-to-identify-whether-a-grammar-is-lrn-lln

A good read.

---

Thanks @Vishal_kumar98.

---

none of options are right

Answer 1

• $S\alpha \to$

This violates the condition of context-free grammar that the $\text{LHS}$ must be a single non-terminal symbol. 

•  $S\alpha \to b$

This violates even the weaker requirement for CSG that the length of $\text{RHS}$ of a production must be at least same as that of $\text{LHS}$. So, the grammar is not even context-sensitive.

Ref: https://stackoverflow.com/questions/8236422/context-free-grammars-versus-context-sensitive-grammars

Comments

@VS

oh.. yeah :D

I didnt knew that ... my bad :)

---

in  csg  , lhs<= rhs  ,  tis grammar is violating tis condition , how csg   ??

---

yes.i think none of options are correct as CSG is also not satisfied.

Answer 2

S ∝→ [violates context free]
Because LHS must be single non-terminal symbol.
S ∝→ b [violates CSG]
→ Length of RHS production must be atleast same as that of LHS.

Extra information is added to the state by redefining items to include a terminal symbol as second component in this type of grammar.
Ex: [A → αβa]
A → αβa is a production, a is a terminal (or) right end marker $, such an object is called LR(k).
So, answer is (D) i.e., LR(k).

Comments

Can you please explain why this is LR(k)? How do we even check if a given grammar is LR(k)?

---

@neel19, Yes same question.. If anyone has  answer : “ How to check if given grammar is LR(k)/ not ” Please reply! @King Suleiman

---

A grammar which is $LR(k)$ has to be Context Free in the first place. So the grammar being unrestricted grammar (Type 0), is not context free (Type 2) and hence not even $LR(k)$. This question has all options wrong.

Answer 3

According To Chomsky Hierarchy

For CFG L.H.S side should be Single variable,production form is like

S->A where S belongs to Variable and A belongs to Variable and Terminal.(L.H.S sholud be single variable).In Production 4 condition violate.

In Case Of Regular Grammer Same thing follow and some additional also,but L.H.S their should be Single Variable.

In Case Of Context Sensitive

Lets X->Y then

|X|<=|Y|( length of x should be less than or equal to Y).this condition is violate in Production 4 where |Sa|>|b|.

option left only D

Answer 4

this is an unrestricted grammer and for grammer being LR(K)  it must be first cfg which it is not therefore no option is the answer for this question the question is wrong

Answer 5

We been given that 

S(alpha) -> b

 This can't be context free as context free language doesn't have a terminal on LHS.(thats why its called context free means free from context around LHS but here in context with S we are also having 'alpha' so can't be context free).Now lets come to context sensative ,this also can't be the case as we know that for context sensative we must have length of RHS >= length of LHS but here RHS has just one element 'b' and LHS has 2 elements S and alpha so this cant be the case.

 

If its not context free then foresure its not regular.

 

THUS (d)

Answer 6

first three op[tion are because of Sa-->

but why D is correct??

So option d say garramer is LR(k) means there is not SR and RR conflict check LR(1) DFA

Comments

LR(k) corresponds to DCFL

And every Dcfl is a CFL

Given grammar is not CFL so no chance of LR(K)