in Compiler Design recategorized by
14,883 views
34 votes
34 votes

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)$
in Compiler Design recategorized by
14.9k views

4 Comments

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

3 Answers

50 votes
50 votes
Best answer
  • $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

edited by
by

4 Comments

@VS

oh.. yeah :D

I didnt knew that ... my bad :)
0
0
in  csg  , lhs<= rhs  ,  tis grammar is violating tis condition , how csg   ??
0
0
yes.i think none of options are correct as CSG is also not satisfied.
3
3
4 votes
4 votes

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)?
0
0

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

0
0
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.
2
2
1 vote
1 vote
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:

Related questions