Geschrieben von ubik am 29.04.2020 um 12:15:
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?