COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
S
|
|
|
A
|
|
|
A
|
|
|
B
|
Detailed explanation-1: -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.
Detailed explanation-2: -A symbol can be useless if it does not appear on the right-hand side of the production rule and does not take part in the derivation of any string. That symbol is known as a useless symbol.
Detailed explanation-3: -Step 1: To remove A → B, add production A → x to the grammar rule whenever B → x occurs in the grammar. Step 2: Delete A → B from the grammar. Step 3: Repeat the first and the second steps until all the unit productions are removed.
Detailed explanation-4: -A variable X in a context-free grammar is called useless if it doesn’t occur in any derivation of a word from that grammar. Here is an easy algorithm to eliminate useless variable from CFGs. Call a variable generating if it derives a string of terminals.