Redirected
retagged by
9,880 views
6 votes
6 votes

Consider the grammar

  • $S \rightarrow ABCc \mid bc$
  • $BA \rightarrow AB$
  • $Bb \rightarrow bb$
  • $Ab \rightarrow ab$
  • $Aa \rightarrow aa$

Which of the following sentences can be derived by this grammar?

  1. abc
  2. aab
  3. abcc
  4. abbc
retagged by

7 Answers

19 votes
19 votes

$C$ is useless in $S \to ABCc$ so remove it.

$S \to ABc$

Now see each of remaining production

$ Bb \to bb $ ( i.e. $ B \to b $)

$ Ab \to ab $ (i.e.$ A \to a $)

$ Aa \to aa $ (i.e. $ A \to a $)

So

$ S \to ABc \to abc $

Hence Option A is correct.

From @ManojK comment. 

12 votes
12 votes
$C$ is a useless symbol, since it cannot derive any terminal. Hence, the production $S \rightarrow ABCc$ becomes obsolete. This causes all other symbols to become unreachable from $S$, they are also identified as obsolete!

Therefore we can only derive $bc$ from this grammar.
Answer:

Related questions

44 votes
44 votes
5 answers
1
Kathleen asked Sep 14, 2014
16,886 views
More than one word are put in one cache block to:exploit the temporal locality of reference in a programexploit the spatial locality of reference in a programreduce the m...
2 votes
2 votes
2 answers
2
go_editor asked Jun 13, 2016
4,282 views
In C, what is the effect of a negative number in a field width specifier?the values are displayed right justifiedthe values are displayed centeredthe values are displayed...
7 votes
7 votes
4 answers
3
go_editor asked Jun 13, 2016
3,225 views
Repeated execution of simple computation may cause compounding ofround-off errorssyntax errorsrun-time errorslogic errors
8 votes
8 votes
1 answer
4
go_editor asked Jun 13, 2016
3,963 views
Consider the graph shown in the figure below:Which of the following is a valid strong component?$a, c, d$$a, b, d$$b, c, d$$a, b, c$