retagged by
613 views
3 votes
3 votes

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.
retagged by

Please log in or register to answer this question.

Related questions