Question

true/false

21 Uncountable infinity (for example, the cardinality of the real numbers). No Countable infinity (for example, the cardinality of the integers) ? All strings over the alphabet ?. CFG Context-free Grammar CFL Context-free Language L(G) The language generated by a CFG G. L(M) The language accepted by the automaton M. PDA Pushdown Automaton/Automata ISI The cardinality of set S. For example, I01 -o, and if S is an infinite set, ISI could be No or J1 L <M> L(M) 8. Rice's theorem can prove that L e D. 37. L = { <M,M.> : L(M1) = L(M2)). Rice's theorem can prove that L e D. F 36,

Answer 1

36. True.

$L=\left \{ \left \langle M\right \rangle:L\left ( M \right )=\left \{ \epsilon \right \} \right \}$ .

In accordance to Rice's theorem, $T_{yes}\ for\ \{\epsilon \}$ , and $T_{no}\ for\ \sum ^* (\epsilon \subset \sum ^*).$

Hence L is not Turing Recognizable (not recursively enumerable). Thus $L\notin D$ .

37. False. Rice's theorem cannot prove that L is Turing Recognizable or not.