0 Daumen
51 Aufrufe

Aufgabe:

1)
Screenshot 2024-01-31 174235.png

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} \)


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}

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)

Screenshot 2024-01-31 173835.png

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} \)



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:


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

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community