Automata Theory Questions and Answers – CFG-Eliminating Useless Symbols

This set of Automata Theory Assessment Questions and Answers 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

Answer: a
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

Answer: d
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

Answer: c
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.
advertisement
advertisement

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

Answer: a
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

Answer: c
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.
Note: Join free Sanfoundry classes at Telegram or Youtube

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

Answer: b
Explanation: Use a dependency graph to find which variable is reachable and which is not.
The number of variables reachable from the Starting Variable is 1

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

Answer: d
Explanation: Inorder to simplify the grammar all of the process including the removal of null productions, unit productions and useless symbols is necessary.
advertisement

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

Answer: a
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

advertisement

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

Answer: a
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

Answer: c
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 Assessment Questions, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.