recategorized by
18,080 views
38 votes
38 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)$
recategorized by

3 Answers

Best answer
55 votes
55 votes
  • $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
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).

1 votes
1 votes
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

23 votes
23 votes
4 answers
2
Kathleen asked Oct 8, 2014
6,550 views
Translate the arithmetic expression $a^\ast -(b+c)$ into syntax tree.A grammar is said to have cycles if it is the case that $A \overset{+}{\Rightarrow} A$ Show that no g...
44 votes
44 votes
1 answer
3