ubik
Mitglied
Dabei seit: 10.04.2015
Beiträge: 41
 |
|
| Beziehungen zwischen der Klassifikation von Sprachen |
     |
Hallo,
ich studiere gerade an der FernUni Hagen.
Nun habe ich eine Frage.
In den KE 5 bis 7 von "Grundlagen der Theoretischen Informatik" kommen Aussagen vor wie:
| Zitat: |
| Die Sprache HALT ist nicht entscheidbar und nicht co-aufzählbar. |
Ich habe mir dann eine Tabelle aufgeschrieben, die folgende Spalten hat:
| Zitat: |
| Sprache | NTIME(n) | Reguläre Sprache | Kontextfreie Sprache | E (entscheidbar) | A (aufzählbar) | co-A | Abzählbar | co-Abzählbar | TIME(n^10) | DPSACE(n) | P | NP |
Nun muss man aus der Aussage, dass HALT nicht entscheidbar und nicht co-aufzählbar ist, irgendwie die restlichen Spalten auswerten.
Dazu habe ich mir eine Teilmengenbeziehung (siehe Anhang) aufgemalt.
Nun hätte ich mehrere Fragen:
- Ist die Teilmengenbeziehung von dem PDF, das im Anhang ist, so richtig?
- Gibt es irgendwo eine Grafik im Internet, die aufzeigt, wie die Sprachen miteinander zusammenhängen?
- Bedeutet "entscheidbar" das Gleiche wie "erkennbar"?
- Angenommen, eine Sprache ist nicht entscheidbar. Welche Auswirkung hat das auf die restlichen Spalten?
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von ubik: 29.04.2020 12:16.
|
|
