14,883 views

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:

1. Context free
2. Regular
3. Context sensitive
4. $LR(k)$

The production Sα→ b indicates that the grammar is not regular, not context-free, and not context-sensitive. Anyone plz explain option D.
Thanks @Vishal_kumar98.

• $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.

by

@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.

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). ### 4 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.
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