If we can automate an algorithm to run on a machine so that it can give us answer to the underlying problem or complement of it then the problem is called decidable. More importantly the algorithm must have to stop in finite time.
A) CNF is a form of CFL grammar. Using CNF we need only 2n-1 steps for any derivation of string where n = | string |. This is decidable.
B) This is indirectly asking whether finding useless symbol in CFG is decidable or not ? It is possible to automate this elimination procedure which means decidable.
LINK
C) Finiteness problem of CFL (or CFG) decidable, because we can check the existence of loops in the dependency graph over the non terminals.
ans : D)
Regarding option A)
- A string is generated by CNF or Not ?
- Whether a string belongs to the language generated by a CNF ?
These are two different questions. They have different solutions.
For checking whether a string is generated by a CNF ? => Procedure takes $2n-1$ steps where n is the string length.
On the other hand,
For checking whether a string belongs to a language generated by a given CNF or CFG ? => CYK algorithm $O(n^{3})$