search
Log In
3 votes
252 views

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.
in Theory of Computation 252 views

Please log in or register to answer this question.

Related questions

1 vote
0 answers
1
99 views
Say that a variable $A$ in $CFG \:G$ is necessary if it appears in every derivation of some string $w \in G$. Let $NECESSARY_{CFG} = \{\langle G, A\rangle \mid \text{A is a necessary variable in G}\}$. Show that $NECESSARY_{CFG}$ is Turing-recognizable. Show that $NECESSARY_{CFG} $is undecidable.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 99 views
0 votes
0 answers
4
57 views
Let $A$ be a Turing-recognizable language consisting of descriptions of Turing machines, $\{ \langle M_{1}\rangle,\langle M_{2}\rangle,\dots\}$, where every $M_{i}$ is a decider. Prove that some decidable language $D$ is not decided by any decider $M_{i}$ whose description appears in $A$. (Hint: You may find it helpful to consider an enumerator for $A$.)
asked Oct 17, 2019 in Theory of Computation Lakshman Patel RJIT 57 views
...