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)

Komplementäres Leerheitsproblem?

Wie sieht es mit dem komplementärem Problem $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 09:48, 12. Jun. 2009 (CEST)

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: $\neg Leerheitsproblem_{TM}=\{M|L(M)\neq \emptyset \}$ (Übrigens ist es somit semi-entscheidbar für Turingmaschinen), siehe [1]

Komplexität d. Leerheitsproblems beim Markierungsalgorithmus

Sollte das mit diesem Algorithmus nicht O(|Q| + |E|) sein? (nicht signierter Beitrag von 141.76.184.230 (Diskussion) 19:42, 10. Okt. 2011 (CEST))