Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Beziehungen zwischen der Klassifikation von Sprachen » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Beziehungen zwischen der Klassifikation von Sprachen
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
ubik
Mitglied


Dabei seit: 10.04.2015
Beiträge: 41

Beziehungen zwischen der Klassifikation von Sprachen Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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?


Dateianhang:
zip Sprachen und ihre Mengenbeziehungen.zip (28,25 KB, 32 mal heruntergeladen)

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von ubik: 29.04.2020 12:16.

29.04.2020 12:15 ubik ist offline E-Mail an ubik senden Beiträge von ubik suchen Nehmen Sie ubik in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Beziehungen zwischen der Klassifikation von Sprachen