(Solved): Classifying Languages as Regular/CF/Decidable/Recognizable (Or Not) Draw the Chomsky hierarchy wit ...

Classifying Languages as Regular/CF/Decidable/Recognizable (Or Not) Draw the Chomsky hierarchy with regions for the classes of regular, context-free, decidable, recognizable, corecognizable, and neither recognizable nor corecognizable. Classify each of the following languages over \( \Sigma=\{0,1\} \) in the Chomsky hierarchy and prove your classifications: \[ \begin{array}{l} L_{0}=\left\{w \in\{0,1\}^{*} \mid w \text { contains } 11 \text { as a substring or ends with } 0\right\} \\ L_{1}=\left\{1^{n} 0^{m}(10)^{m} 0^{n} \mid n, m \geq 0\right\} \\ L_{2}=\left\{w \in\{0,1\}^{*} \mid w=w^{\mathcal{R}} \text { and } w \text { has at least as many } 1 \text { s as } 0 \text { s }\right\} \\ L_{3}=\{\langle M\rangle \mid M \text { is a TM that is not a decider }\} \end{array} \]