I. Given a CFG $G$, whether $G$ contains any useless symbols.
- DECIDABLE. A useless symbol is one that is either non-generating (cannot derive a terminal string) or non-reachable (cannot be reached from the Start symbol). There are standard, terminating algorithms to find both sets of symbols. Any symbol not in both sets is useless. This is a standard procedure in compiler design.
II. Given a TM $M$, whether the language $L(M)$ is Recursive.
- UNDECIDABLE. This is a non-trivial property of the language $L(M)$, so we can apply Rice's Theorem. The property "is recursive" is non-trivial because some recursively enumerable languages are recursive (e.g., $\emptyset, a^n b^n$ ), and some are not (e.g., the Halting Problem). Since the property is non-trivial, it is undecidable.
III. Given a PDA $P$ and a DFA $A$, whether $L(P)=L(A)$.
- UNDECIDABLE. This is the equivalence problem between a Context-Free Language (CFL) and a Regular Language (RL). This problem is known to be undecidable. We can prove this by reducing the Universality Problem for CFLs (which is undecidable) to it. The Universality Problem asks: "Given a PDA $P$, is $L(P)=\Sigma^*$ ?" We can solve this if we can solve Problem III: We just create a simple DFA $A$ that accepts $\Sigma^*$, and then ask our decider for Problem III if $L(P)=L(A)$. Since the Universality Problem is undecidable, Problem III must also be undecidable.
IV. Whether a given instance of PCP has a match.
- UNDECIDABLE. This is the Post's Correspondence Problem (PCP). It is a classic and very famous undecidable problem, often used to prove other problems (like ambiguity in CFGs) are undecidable.
