UGCNET CSE December 2022: 83

Question

 

What is the safest order while simplifying Context Free Grammar?

• A. Elimination of $\varepsilon$-productions, Unit productions and then Useless symbols \& productions.
• B. Elimination of useless symbols \& productions, $\varepsilon$-productions and then Unit productions.
• C. Elimination of Unit productions, $\varepsilon$-productions and then Useless symbols and productions.
• D. Elimination of $\varepsilon$-productions, Useless symbols and productions and then Unit productions.

(Option $1[39629]) 1$
(Option $2[39630]) 2$
(Option $3[39631]) 3$
(Option $4 [39632]) 4$

Answer Given by Candidate: $2$

Answer 1

$(A)$ 

1. Elimination of ε-productions (A): ε-productions can potentially introduce new unit productions into the grammar, so it’s usually better to eliminate these first.
2. Elimination of unit productions (B): The removal of unit productions could potentially make a previously useful production into a useless one, so it’s better to handle unit productions before dealing with useless ones.
3. Elimination of useless symbols & productions (C): This is typically done last, as the previous elimination steps could potentially create new useless symbols or productions that need to be eliminated.