Aufgabe:
1)
Text erkannt:
Wir betrachten die formale Sprache
\( L_{3}:=\{\langle D, M\rangle \mid D \) ist ein DEA, \( M \) ist eine TM und \( L(D) \supseteq L(M)\} \).
Zeigen Sie: \( L_{3} \in \mathbb{A}^{c o} \backslash \mathbb{A} \)
2)
Text erkannt:
Wir betrachten die Sprache
\( L_{5}=\left\{\langle M\rangle \mid M(w) \uparrow \text { für alle } w \in \Sigma^{*} \text { mit }|w| \geq 100\right\} . \)
Zeigen Sie: \( L_{5} \in \mathbb{A}^{c o} \backslash \mathbb{A} \)
Problem/Ansatz:
Vor allem das 1) wär mir erstmal wichtig zu verstehen, dann kommt man ja wohl auch auf Aufgabe 2) denke ich.
Ich weiß, wie man mit einer Reduktion zeigen kann, dass etwas NICHT co-aufzählbar oder aufzählbar ist, aber ich weiß nicht, wie man zeigt, dass etwas wohl co-aufzählbar ist.
Ich hatte erst versucht, bei Aufgabe 1 einfach das Komplement der Sprache zu nehmen (also L(D) ist echte Teilmenge von L(M) und dann einen Aufzähler dafür zu bauen. Und dann ist ja L_quer aus A und dementsprechend L aus A-co, dachte ich.
Ich hab auch einen gefunden, aber nach dem gleichen Muster kann ich halt dann auch einen bauen für die normale Richtung und dann wäre L also sowohl in A als auch in A-co, aber das ist ja falsch.
Ich bin leider etwas verzweifelt, weil das glaube ich echt wohl wichtig ist, vielleicht kann mir ja jemand helfen
