Wie kann ich das Diagramm eines DFA in eine Turing-Maschine konvertieren? Muss ich die Sprache finden, die der DFA akzeptiert und dann die Turing-Maschine erstellen? Oder gibt es einen direkten Weg?Wie konvertiert man eine DFA zu einer Turing-Maschine?
Vielen Dank.
Jede Transition in einem DFA liest ein Zeichen der Eingabe, folgt einem Übergang und springt dann zum nächsten Zeichen der Eingabe. Sobald alle Eingaben gelesen wurden, akzeptiert das DFA, ob es in einem akzeptierenden Zustand ist und lehnt es ab.
Sie können dies direkt mit einer Turing-Maschine simulieren. Erstellen Sie die Zustandsüberwachung der Turing-Maschine, indem Sie für jeden Zustand im DFA einen Zustand erstellen. Ersetzen Sie für jeden Übergang im DFA auf dem Zeichen c diesen Übergang im TM mit einem Zeichen, das beim Lesen von Zeichen c ein beliebiges Zeichen auf das Band zurückschreibt (egal was) und dann den Bandkopf nach rechts bewegt (zum nächsten Punkt auf dem Band). Dann führe für jeden Zustand einen Übergang auf das leere Symbol von diesem Zustand entweder in den Annahmezustand des TM oder in den Zurückweisungszustand des TM ein (basierend darauf, ob dieser Zustand akzeptiert oder zurückweist). Dieses TM führt das DFA effektiv aus, indem es manuell über die Eingabezeichenfolge wechselt und schließlich entscheidet, ob es am Ende des Laufs akzeptiert oder abgelehnt wird.
Hoffe, das hilft!
Wann passiert, wenn ein Zeichen c gelesen wird, das nicht zu einem Zustandsübergang führt? Ist ein beliebiger Buchstabe geschrieben und bewegt sich der Tonkopf noch richtig? – Paradox
@Paradox Unter den meisten Definitionen eines DFA muss im DFA für jedes Zeichen und jeden Status ein Übergang definiert sein. Ähnlich sind die meisten TMs so definiert, dass Sie einschränken können, welche Arten von Symbolen als Eingabe eingegeben werden können, und Sie sich nie darum kümmern müssen: Jedes TM-Symbol, das gefunden werden könnte, wäre etwas, das das DFA haben würde Übergang definiert für. Wenn Sie diese Einschränkung nicht haben, können Sie sie einfach ablehnen - die Sprache des DFA ist darauf beschränkt, nur Buchstaben aus dem Alphabet zu verwenden. Wenn Sie also ein fremdes Zeichen sehen, wissen Sie, dass die Zeichenfolge nicht in der Sprache ist. – templatetypedef