This post has been edited 1 times, last edit by "Peter" (Sep 1st 2010, 9:26am)
This post has been edited 1 times, last edit by "Xular" (Aug 31st 2010, 4:00pm)
Ich würde sagen, es gibt keinen DEA, der entscheiden kann, ob bei einem Wort xy |x| = |y| ist,
weil ein DEA nunmal keinen Speicher hat: Er kann nicht speichern, wie lang das Wort x ist um zu prüfen, ob y genauso lang ist.
This post has been edited 1 times, last edit by "Panoramix" (Aug 31st 2010, 5:49pm)
This post has been edited 2 times, last edit by "FSW16" (Aug 31st 2010, 10:42pm)
Akzeptierbar ist definiert als: Es gibt eine Turingmaschine, die genau bei den Wörtern aus der Sprache einen Endzustand erreicht (und dann anhält) und bei den restlichen Wörtern nie einen Endzustand erreicht (und aber ewig läuft, weil sie ja nicht gesagt bekommt, dass sie anhalten soll).
Semi-entscheidbar ist definiert als: Es gibt eine Turingmaschine, die bei den Wörtern aus der Sprache "1" ausgibt und bei allen anderen Wörtern ewig läuft.