Rekursiv aufzählbar < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Zeigen oder widerlegen Sie die folgende Aussage: Wenn [mm] $L_1$ [/mm] und [mm] $L_2$ [/mm] rekursiv aufzählbar sind, dann sind es auch [mm] $L_1 \cap$ [/mm] und [mm] $L_1 \cup L_2$. [/mm] |
Hi Leute!
Ich hab Probleme mit dieser Aufgabe. Das erste Problem ist, ich weiß nicht ob meine Umformung in eine Art "Gleichung" korrekt ist. Ich hätte das nun als erste so gemacht:
[mm] $L_1$ [/mm] und [mm] $L_2$ [/mm] rekursiv aufzählbar [mm] $\Leftrightarrow$ $L_1 \cap L_2$ [/mm] rekursiv aufzählbar
Beweis:
[mm] "$\Rightarrow$"
[/mm]
Sei [mm] $L_1$ [/mm] rekursiv aufzählbar und sei [mm] $L_2$ [/mm] rekursiv aufzählbar, d.h. es gibt eine TM [mm] $M_1$ [/mm] die [mm] $L_1$ [/mm] akzeptiert und es gibt eine TM [mm] $M_2$ [/mm] die [mm] $L_2$ [/mm] akzeptiert.
[mm] "$\Leftarrow$"
[/mm]
Da der Schnitt gegenüber Sprachen die rekursiv aufzählbar sind abgeschlossen ist, ist nun bewiesen, dass die eingeführte Beziehung (durch die Aufgabe gegeben) [mm] "$\Leftrightarrow$ [/mm] gilt.
Ist das so richtig?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Do 06.06.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
