Forum
 
Fragen
 
Suchen
 
Über Uns
 
 

Beziehungen zwischen der Klassifikation von Sprachen
Neue Frage »

29.04.2020, 12:15 Auf diesen Beitrag antworten »
ubik 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?
 
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Beziehungen zwischen der Klassifikation von Sprachen

 
© 2005-2019 bei Informatikerboard.de | Archiv, alt, neueste | Kontakt | Jugendschutz | Nutzungsbedingungen