Aufgabe:
- \( A_{1}=\left\{w \mid M_{w}\right. \) hält auf \( w \) und hat mindestens 128 Zustände \( \} \)
\( -A_{2}=\left\{\left.w \in\{0,1,2\}^{*}|| w\right|_{0}=|w|_{2}\right\} \)
- \( A_{3}=\left\{w \mid M_{w}\right. \) hält nicht auf Eingabe \( \left.w\right\} \)
- \( A_{4}=\left\{\left.w \in\{0,1,2\}^{*}|| w_{0}|=| w\right|_{1}=|w|_{2}\right\} \)
- \( A_{5}=\left\{a^{n} b^{m} \mid n \not \equiv m(\bmod 42)\right\} \)
\( -A_{6}=\left\{w \in\{0,1\}^{*} \mid\right. \) enthält das Teilwort 111 und endet auf 11\( \} \)
Zu welcher Sprache der Chomsky Hierachie gehören diese Sprachen?
Problem/Ansatz:
A1 ist Typ0
A2 Typ 2
A3 Typ 0
A4 typ 2
A5 Typ 3
A6 Typ 1
STimmt das ?
