Allgemeine Fragen zu Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 14:11 Mi 04.03.2015 | | Autor: | Mathe93 |
| Aufgabe | 1) Wenn R regulär ist und L Kontextfrei, dann ist L [mm] \cap [/mm] R kontextfrei.
2) Der Schnitt zweier aufzählbarer Sprachen ist aufzählbar.
3) Die Vereinigung zweier entscheidbarer Sprachen ist entscheidbar.
4) Das Komplement einer aufzählbaren Sprache ist aufzählbar.
5) Wenn A [mm] \in [/mm] Regulär und [mm] B\in [/mm] Entscheidbar dann ist A [mm] \cup [/mm] B [mm] \in [/mm] Entscheidbar
6) Wenn A [mm] \in [/mm] co-Aufzählbar dann ist [mm] A\cap A_{TM} [/mm] nicht entscheidbar
7) Geben Sie eine Sprache aus NP an. Begründen Sie ihre Antwort kurz.
8) Geben Sie eine Sprache an, die nicht in NP liegt. Begründen Sie ihre Antwort kurz.
9) Beweisen Sie, dass NP unter Schnitt abgeschlossen ist. |
Ich habe mich mal ein wenig selbst dran versucht;
Zu 1) /
Zu 2) Aus der Vorlesung geht hervor das die aufzählbaren Sprachen unter dem Schnitt abgeschlossen sind aber wie beweise ich das konkret?
Zu 3) Ich weiß das entscheidbare Sprachen unter dem Schnitt abgeschlossen sind.
Zu 4) Könnte man hierbei nicht mit dem Halte Problem argumentieren?
Zu 5)Diese Aussage stimmt denn jede REG Sprache ist entscheidbar und entscheidbar ist unter Vereinigung abgeschlossen.
Zu 6)/
Zu 7)/
Zu 8)/
Zu 9)/
Vorallem bei NP und P komme ich nicht so richtig vorran.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Fr 06.03.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
