Michael Sipser Edition 3 Exercise 5 Question 36 (Page No. 242)

Question

Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$.

1. Show that $MIN_{CFG}$ is $T-$recognizable.
2. Show that $MIN_{CFG}$ is undecidable.