Register

Test by Bikram | Theory of Computation | Test 1 | Question: 14

• edited by
433 views
0 votes
0 votes

Consider the grammar given below :

  • $S \rightarrow AB \mid DA$
  • $B \rightarrow BCD \mid ABD \mid CC \mid b$
  • $A \rightarrow a \mid BC$
  • $C \rightarrow aBD \mid a$
  • $C \rightarrow aBCAD \mid DaB$
  • $A \rightarrow aBCAD \mid Da$
  • $A \rightarrow aBD \mid aCBD \mid aSBCD$ 


The following non terminal is useless in the grammar (as non terminal strings can be derived from it):

  1. $D$
  2. $C$
  3. $B$
  4. $A$
• edited by
User Avatar

2 Answers

Best answer
1 votes
1 votes
S is the starting variable. Two conditions to be checked:
i. A,B,C and D all 4 are rechable from start variable
ii But, A,B, and C only can generate terminal(s)

Hence D is useless, though it's rechable from S but can't generate any terminal, furthermore, it doesn't have any production in given grammar.
• selected by
User Avatar
1 votes
1 votes
option a

as d does not generate any string .
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

6 votes
6 votes
2 answers
1
Bikram asked Nov 26, 2016
1,232 views
Test by Bikram | Theory of Computation | Test 1 | Question: 30
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is: Decidable Undecidable but semi-decidable Not even semi-decidable Indeterminable
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is:DecidableUndecidable but semi-decida...
User Avatar
0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
314 views
Test by Bikram | Theory of Computation | Test 1 | Question: 29
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an: Decidable problem Undecidable problem Cannot ascertain None
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an:Decidable prob...
User Avatar
0 votes
0 votes
1 answer
3
Bikram asked Nov 26, 2016
225 views
Test by Bikram | Theory of Computation | Test 1 | Question: 28
Recursive Enumerable Languages are NOT closed under : Union Intersection Complement Homomorphism
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
User Avatar
0 votes
0 votes
1 answer
4
Bikram asked Nov 26, 2016
221 views
Test by Bikram | Theory of Computation | Test 1 | Question: 27
If $S$ and $T$ are languages over $\Sigma =\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$ respectively, then which of the following options is CORRECT? $S \subset T$ $T \subset S$ $S = T$ $S \cap T = \emptyset$
If $S$ and $T$ are languages over $\Sigma =\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$ respectively, then which of the following options is ...
User Avatar
Link Copied!