Konstruktion, die die Spracheeine nicht deterministische Turingmaschine
L entscheidet = {w∈Σ * | w = u u u ∈Σ *}
wenn ich Hilfe Erklärung der Schritte bekommen konnte, wie die NDTM (sprachlich) zu konstruieren, ich glaube ich das Diagramm ziehen könnte, aber ich könnte nicht mit einer Antwort kommen ..
danke
von u*u*u (in der Versionsgeschichte gesehen), nehme ich an, was Sie beabsichtigen, ist die Sprache aller Wörter der Form u^3 (u dreimal wiederholt), wobei u eine beliebige Zeichenfolge über dem Alphabet ist .
Unser NDTM muss Zeichenfolgen in der Sprache in mindestens einer Weise akzeptieren, und es darf niemals irgendetwas akzeptieren, das nicht in der Sprache ist. Der Schlüssel ist insbesondere, dass ein NDTM Zeichenfolgen in der Sprache zurückweisen kann, solange ein Pfad durch NDTM jede Zeichenfolge in der Sprache akzeptiert.
Gegeben, unser erster Schritt kann raten über die Länge von u. Der NDTM kann drei Bandsymbole (z. B. durch Schreiben von Versionen der Symbole, die unterstrichen sind) durch nichtdeterministisches Überführen von dem Zustand q0 zu q1 dann q2 an beliebigen Punkten beim Scannen nach rechts markieren. Dann können wir den Bandkopf zurücksetzen und ein deterministisches TM verwenden, um die Frage zu beantworten: Hat der Split, den wir im ersten Schritt erraten haben, eine Zeichenkette des Formats u^3 ergeben?
Dies ist deterministisch, da wir die Abgrenzung von Teilen kennen. Wir können die ersten beiden Teile überprüfen (sagen wir, indem wir zurückspringen und Symbole markieren, die wir bereits bearbeitet haben) und dann die zweiten beiden Teile (mit der gleichen Technik, aber angewandt auf den zweiten und dritten Teil).
Wir haben das Problem auf die Überprüfung reduziert, ob eine Zeichenfolge die Form w|w hat, in der wir die Aufteilung kennen. Diese deterministische TM ist leichter zu finden. Wenn wir es nach dem NDTM setzen, das rät, wie man die ursprüngliche Eingabe aufteilt, erhalten wir einen NDTM, der (und für genau eine Schätzung) eine Zeichenkette des Formulars u^3 akzeptieren kann, aber nichts anderes akzeptieren kann. Das war es, was wir wollten und wir sind fertig.