Question

Which of the following steps are wrong with respect to infiniteness problem?

(a) Remove useless variables

(b) Remove unit and epsilon production

(c) Create dependency graph for variables

(d) If there is a loop in the dependency graph the the language is finite else infinite

I have been asked this question in examination.

My question is based upon Intersection with Regular Languages topic in division Properties of Context Free Languages of Automata Theory

Answer 1

Right option is (d) If there is a loop in the dependency graph the the language is finite else infinite

To explain I would say: If we are able to detect a loop in the formed dependency graph, then the language in infinite.