This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “CFG-Eliminating Useless Symbols”.
1. Suppose A->xBz and B->y, then the simplified grammar would be:
a) A->xyz
b) A->xBz|xyz
c) A->xBz|B|y
d) none of the mentioned
View Answer
Explanation: For the first step, substitute B in first production as it only produces terminal and remove B production as it has already been utilized.
We get A->xBz|xyz and now, as B has no production, we eliminate the terms which hold the variable B, thus the answer remain A->xyz.
2. Given Grammar: S->A, A->aA, A->e, B->bA
Which among the following productions are Useless productions?
a) S->A
b) A->aA
c) A->e
d) B->bA
View Answer
Explanation: Some derivations are not reachable from the starting variable. As B is not reachable from the starting variable, it is a useless symbol and thus, can be eliminated.
3. Given:
S->…->xAy->…->w
if ____________, then A is useful, else useless symbol.
a) A is a non terminal
b) A is a terminal
c) w Î L
d) w Ë L
View Answer
Explanation: Whatever operation we perform in intermediate stages, if the string produced belongs to the language, A is termed as useful and if not, not a useful variable.
4. Given:
S->aSb
S->e
S-> A
A->aA
B->C
C->D
The ratio of number of useless variables to number of useless production is:
a) 1
b) 3/4
c) 2/3
d) 0
View Answer
Explanation: A, B, C, D are the useless symbols in the given grammar as they never tend to lead to a terminal. The productions S-> A, A->aA, B->C, C->D are also termed as useless production as they will never produce a string to the grammar.
5. Given grammar G:
S->aS|A|C
A->a
B->aa
C->aCb
Find the set of variables thet can produce strings only with the set of terminals.
a) {C}
b) {A,B}
c) {A,B,S}
d) None of the mentioned
View Answer
Explanation: First step: Make a set of variables that directly end up with a terminal
Second step: Modify the set with variables that produce the elements of above
generated set.
The rest variables are termed as useless.
6. Given grammar:
S->aS|A
A->a
B->aa
Find the number of variables reachable from the Starting Variable?
a) 0
b) 1
c) 2
d) None of the mentioned
View Answer
Explanation: Use a dependency graph to find which variable is reachable and which is not.
7. Inorder to simplify a context free grammar, we can skip the following operation:
a) Removal of null production
b) Removal of useless symbols
c) Removal of unit productions
d) None of the mentioned
View Answer
Explanation: Inorder to simplify the grammar all of the process including the removal of null productions, unit productions and useless symbols is necessary.
8. Given a Grammar G:
S->aA
A->a
A->B
B->A
B->bb
Which among the following will be the simplified grammar?
a) S->aA|aB, A->a, B->bb
b) S->aA|aB, A->B, B->bb
c) S->aA|aB, A->a, B->A
d) None of the emntioned
View Answer
Explanation: Step 1: Substitute A->B
Step 2: Remove B->B
Step 3: Substitute B->A
Step 4: Remove Repeated productions
9. Simplify the given grammar:
A-> a| aaA| abBc
B-> abba| b
a) A-> a| aaA| ababbAc| abbc
b) A-> a| aaA| ababbAc| abbc, B-> abba|b
c) A-> a| aaA| abbc, B->abba
d) None of the mentioned
View Answer
Explanation: Using the substitution rules, we can simply eradicate what is useless and thus produce the simplified result i.e. A-> a| aaA| ababbAc| abbc.
10. In context to the process of removing useless symbols, which of the following is correct?
a) We remove the Nullable variables
b) We eliminate the unit productions
c) We eliminate products which yield no terminals
d) All of the mentioned
View Answer
Explanation: In the process of removal of useless symbols, we want to remove productions that can never take part in any derivation.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Practice Computer Science MCQs
- Check Computer Science Books
- Check Automata Theory Books
- Apply for Computer Science Internship
