Question

A symbol X is called to be useful if and only if its is:

(a) generating

(b) reachable

(c) both generating and reachable

(d) none of the mentioned

I have been asked this question during an interview.

This interesting question is from Inferences to Trees, Trees to Derivations in division Context Free Grammars and Languages of Automata Theory

Answer 1

The correct option is (c) both generating and reachable

The best I can explain: For a symbol X to be useful, it has to be both reachable and generating i.e.

S->* aXb -> * w where w belongs to T*.