How can the decision algorithm be constructed L for deciding whether context-free language is finite? CFGG

(a) By constructing redundant in CNF L generating language −−

(b) By constructing non-redundant CFG G in CNF L generating language CFGG

(c) By constructing non-redundant in CNF L − {∧}(∧ generating language stands for null) Which of the following is correct?

1. A(a) only
2. B(b) only
3. C(c) only
4. DNone of (a), (b) and (c)

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. (c) only

Explanation

Build a non-redundant CNF grammar for L − {ε} and check its variable-dependency graph for cycles: finite iff there are none.