Diskussion:Leerheitsproblem

Also, die Frage ist doch eher ob die Erklärung des Problems hier das Problem auch erklärt ??? --Creando 00:01, 6. Jul 2004 (CEST)

Wie sieht es mit dem komplementärem Problem ${\displaystyle L=\Sigma ^{*}}$ aus? Es existiert weder eine Seite dazu noch wird hier etwas dazu gesagt

Doch, was du suchst, nennt sich WORTPROBLEM. MFG --F GX Diskussion:Leerheitsproblem#c-F GX-2009-06-12T07:48:00.000Z-Komplementäres Leerheitsproblem?11Beantworten

Nein, das ist nicht das selbe, das Wortproblem ist: ist w Element von L.

Das Komplement wäre (bei TM): Akzeptiert es einige Wörter. Besser ausgedrückt: ${\displaystyle \neg Leerheitsproblem_{TM}=\{M|L(M)\neq \emptyset \}}$ (Übrigens ist es somit semi-entscheidbar für Turingmaschinen), siehe [1]

Sollte das mit diesem Algorithmus nicht O(|Q| + |E|) sein? (nicht signierter Beitrag von 141.76.184.230 (Diskussion) Diskussion:Leerheitsproblem#c-141.76.184.230-2011-10-10T17:42:00.000Z-Komplexität d. Leerheitsproblems beim Markierungsalgorithmus11) Beantworten