Frage:
Chomsky-Hierarchie
Geben Sie für folgende Sprachen jeweils (i) eine Grammatik \( G_{i} \) mit \( L\left(G_{i}\right)=L_{i}, 1 \leq i \leq \) 3 und möglichst großem Typ an und (ii) geben Sie explizit den maximalen Typ Ihrer Grammatik an. Begründen Sie Ihre Antworten, insbesondere, warum Ihre Grammatik von keinem größeren Typ ist.
(a) \( L_{1}=\left\{a^{n} b^{m} \mid n, m \geq 2\right\} \subseteq\{a, b\}^{*} \)
(b) \( L_{2}=\left\{a b a^{n+2} b a \mid n \geq 1\right\} \subseteq\{a, b\}^{*} \)
(c) \( L_{3}=\left\{0^{2 n} 110(01)^{n} \mid n \geq 0\right\} \subseteq\{0,1\}^{*} \)