The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+21 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)$
asked in Compiler Design by Veteran (59.8k points)
edited by | 2.7k views
Isn't this production violating CSL property of |LHS| <= |RHS| ?

$S\alpha\ \rightarrow b$
yes.. I'm having the same doubt.. Plz let me know after your doubt gets cleared. Thanks !

Agree @ Tuhin Dutta 

1 Answer

+33 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.


answered by Veteran (396k points)
edited by
is ∝ a terminal?
∝ is Non terminal, teminal as well....
Yes. alpha is a sequence of terminals and non-terminals.
In CSL by definition, length of LHS of production is less than RHS ? How CSL then ?
@pC sir, why? how ? LR(k) ? It's not even CFG
@sudarshna  can u give me hint about how grammers are joined wid  diffrent parsers.
one doubt sir, if if Alpha is sequence of terminals or non terminals then how CSL  as in CSL every production should be , if X--->Y then |x| <= |y| so this also voilates the condition of CSL  as given S aplha --> b  ???
@piya  i know u r correct but other then this we don't have better choice. bcz we always belive to a  take strong answer so due to its violate cfg then we go upward in chomasky hirearchy  then we have only csl  otherwise if option is unrestricted grammer(type 0)  then i will go wid that .
Ok sir...  N wht is lr(k)?
plz dont call me sir.  lr(k)  is a bottom up parser and all bottom parser generate  right most derivation and in this  parser  we parse  the string form bottom to up  fashion .in this question its  some how relevant bcz  some where i red it is equvalent to DPDA means accept dcfl but not cfl .
@arjun sir,
By definition it is a CSL because of the case [email protected]>bdb|bd  (@ being alpha)

BUT if try to analyse the grammer, the production [email protected] will never be used,

Since all productions have terminal symbols only except
Which will produce @@@@@....S on recursion but never ever [email protected] will be seen in any permutation of the grammer.
Also, the rest of the gammer is right recursive therefore I think it should be Regular.

Although in the book it is given as you explained, but still I have this doubt.
It will be very helpful of you to kindly clear it.

The grammar is surely not regular

consider S->@bb

now, @ sequence of terminals and nonterminals

eg @=AAB

then S->AABbb surely not regular


@ is given as terminal not non terminal.

What i am saying is that the production [email protected] will never be used in any derivation for the grammar. Therefore its its useless and will never occur during parsing.

If we ignore that .. then the grammar is right recursive and also we can obtain a RegEx for that

@*([email protected] + [email protected] + ab + b + abb)



∝ is Non terminal, teminal as well....

Please read the above comment by Digvijay sir


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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,126 questions
53,252 answers
70,502 users