 |
 |
 |
 |
 |
 |
Startseite » Forum » Abzählbar unendlich viele kontextfreie Sprachen
Abzählbar unendlich viele kontextfreie Sprachen
Universität / Fachhochschule
Sonstiges
Tags: Abzählbarkeit, Sonstiges, Theoretische Informatik
 
|
  |
|---|
|
Hi, kann mir jemand sagen, wie ich zeigen kann, dass es abzählbar unendlich viele kontextfreie Sprachen über dem Alphabet gibt? Ich meine, ich müsste vermutlich irgendeine längen-lexikographische Ordnung finden um auf die abzubilden allerdings komm ich damit nicht weiter. Gibt es vielleicht irgendeinen Satz, irgendeine Definition die mich schneller ans Ziel führt und mich nicht zwingt eine komplizierte Abbildung zu finden? Hat irgendwer eine gute Lösung für das Problem? Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo benutze Cantors Diagonalverfahren, das kannst du auch einfach zitieren, waagerecht a aa aaa oder senkrecht usw http//de.wikipedia.org/wiki/Cantors_erstes_Diagonalargument Gruß ledum |
 |
|
Ich habe gerade nochmal über die Aufgabe nachgedacht und würde fast behaupten, dass die Menge möglicherweise nicht abzählbar unendlich ist sondern überabzählbar unendlich. Da zwar die Wörter die man aus bilden kann abzählbar unendlich sind, allerdings die kontextfreien Sprachen die man daraus bilden kann müssten dann ähnlich der Potenzmenge von sein. (Bis auf dass die entfallen, die nicht der kontextfreien Eigenschaft entsprechen.) Wenn ich mit dieser Vermutung richtig liegen sollte (was mir möglicherweise irgendjemand bestätigen kann - wie würde ich dies dann zeigen, da ich für Überabzählbarkeit kein so tolles Schema aufbauen kann wie ledum mir vorgeschlagen hat (Danke dafür)) |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1211677
1211651