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 » Antwort erstellen » Hallo Gast [Anmelden|Registrieren]

Antwort erstellen
Benutzername: (du bist nicht eingeloggt!)
Thema:
Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33
smileWinkDaumen hoch
verwirrtAugenzwinkerngeschockt
Mit ZungeGottunglücklich
Forum Kloppebösegroßes Grinsen
TanzentraurigProst
TeufelSpamWillkommen
LehrerLOL HammerZunge raus
Hilfe 
aktuellen Tag schließen
alle Tags schließen
fettgedruckter Textkursiver Textunterstrichener Text zentrierter Text Hyperlink einfügenE-Mail-Adresse einfügenBild einfügen Zitat einfügenListe erstellen CODE einfügenPHP CODE farbig hervorheben
Spamschutz:
Text aus Bild eingeben
Spamschutz

Der letzte Beitrag
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?


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