Turingmaschinen-Diagramm-Generator kostenlos

So funktioniert’s

Turingmaschinen-Diagramm-Beispiele.

Ein Tool, vier Anfragen. Alle Diagramme unten wurden tatsächlich erstellt.

Ihre Eingabe

Zeichne eine Turingmaschine für den unären Inkrementierer: In q0 wird 1 gelesen, 1 geschrieben und nach rechts gegangen; bei dem Leerzeichen B wird 1 geschrieben, stehen geblieben und der akzeptierende Zustand qa erreicht.

Jetzt ausprobierenÄndere die Maschine so, dass sie stattdessen die letzte unäre 1 löscht.Füge für das Eingabesymbol 0 einen verwerfenden Zustand hinzu.

Zustandsdiagramm · OMG UML 2.5.1 §14 + Harel (1987) statechart · schematex-state

Das Diagramm

Was ein Turingmaschinen-Diagramm ist.

Ein Turingmaschinen-Diagramm ist ein Zustandsdiagramm für eine Maschine, die Symbole auf einem unbeschränkten Band liest und schreibt. Eine Übergangsbeschriftung enthält normalerweise Lesen/Schreiben/Bewegen, etwa 1/0,L: 1 lesen, 0 schreiben und den Kopf nach links bewegen.

Das Diagramm zeigt die Steuerzustände und die Bandoperation, die den jeweils nächsten Zustand auswählt. Akzeptierende und verwerfende Haltezustände machen das Ergebnis der Berechnung eindeutig.

Standard: OMG UML 2.5.1 §14 + Harel (1987) statechart
Engine: schematex-state
Editable: Double-click text, drag nodes
Export: SVG · PNG · PDF

Zustandsdiagramm: Was ein Turingmaschinen-Diagramm ist

Für wen es gedacht ist

Wer Turingmaschinen-Diagramme verwendet.

Studierende der Berechenbarkeitstheorie

Kleine unäre Maschinen zum Üben des Lesens der Übergangsfunktion und der Bandoperationen.

Dozierende für Automatentheorie

Algorithmen zur Markierung, die Sprachen wie a^n b^n erkennen und über endliche Automaten hinausgehen.

Lernende im Bereich Algorithmen

Zweiphasige Bandscans, die zeigen, wie eine Maschine von einem Eingabeblock zum nächsten wechselt.

So funktioniert’s

Wie man ein Turingmaschinen-Diagramm in drei Schritten erstellt.

Beschreiben

Ein Absatz reicht für den Anfang.

“Zeichne eine Turingmaschine für den unären Inkrementierer: In q0 wird 1 gelesen, 1 geschrieben und nach rechts gegangen; bei dem Leerzeichen B wird 1 geschrieben, stehen geblieben und der akzeptierende Zustand qa erreicht.”

Diagramm ansehen

Die passende Engine erstellt das Diagramm.

Änderungen angeben

Für jede Änderung wird eine Version gespeichert.

Ändere die Maschine so, dass sie stattdessen die letzte unäre 1 löscht.

V2 · DRAWN FROM V1, NOTHING RETYPED

FAQ

Häufige Fragen

Was zeigt die Beschriftung eines Turingmaschinen-Übergangs?

Sie zeigt das gelesene Bandsymbol, das geschriebene Symbol und die Richtung, in die sich der Kopf bewegt. 1/B,R bedeutet beispielsweise: 1 lesen, Leerzeichen schreiben und nach rechts gehen.

Wie werden Akzeptier- und Verwerfzustände dargestellt?

Ein akzeptierender Zustand ist ein haltender Endzustand und wird gewöhnlich mit einem Doppelkreis dargestellt. Ein separater Verwerfzustand kann enthalten sein, wenn die Maschine einen ausdrücklich erfolglosen Halt zeigen muss.

Wie beschreibe ich eine Turingmaschine?

Nenne das Eingabealphabet, die Sprache oder Aufgabe und beschreibe dann, was die Maschine in jeder Phase tut: was sie liest, schreibt und überspringt und wann sie anhält.

Was bedeuten L, R und S?

Sie bezeichnen Bandkopfbewegungen: L bewegt sich nach links, R nach rechts und S lässt den Kopf auf der aktuellen Bandzelle stehen.

Kann ein Turingmaschinen-Diagramm einen Markierungsalgorithmus darstellen?

Ja. Benenne die Markierungssymbole und erkläre, welche Eingabesymbole paarweise zugeordnet oder übersprungen werden. Das Zustandsdiagramm kann die Scan-, Markierungs-, Rückkehr- und Prüfphasen zeigen.

Ähnliche Tools