Turingmaschine konstruieren

[Webo]

Hallo zusammen,

ich habe grade ein Problem beim "Konstruieren einer Turingmaschine". Die Aufgabe ist es eine Maschine zu konstruieren, die Wörter aus {a,b}* erkennt, welche die gleiche Anzahl von as wie bs haben.

Mein Gedanke dazu ist:

Vom Startzeichen ausgehend: Wenn ein a das aktuelle Zeichen ist, dann gehe solange weiter, bis ein b kommt (oder halt genau andersrum). Dann ersetze das b und das a durch ein Sonderzeichen und nehme das Zeichen neben a und mache dann das genauso. Wenn das aktuelle Zeichen ein Sonderzeichen ist -> ignorieren. Wenn dann irgendwann kein Gegenstück mehr zu einem a oder b da ist, dann ist das Wort nicht richtig. Wenn nur noch Sonderzeichen da sind ist das Wort "richtig".

Soweit zu meiner Theorie - müsste doch so eigentlich gehen?! Das große Fragezeichen ist jetzt nur noch, wie schreibe ich das jetzt als Turingmaschine. Was mich aufhält ist das "solange weiter gehen" und "wieder zum a zurück". Da hab ich keine Idee, wie ich das aufschreiben sollte.

Vielleicht kann mir von Euch jemand weiterhelfen.


Grüße

Webo

[BUG]

Zum Weitergehen:

Code:

suche_a, a -> nicht_bewegen, a, a_gefunden
suche_a, b -> nach_rechts, b, suche_a
suche_a, SONDERZEICHEN -> nach_rechts, SONDERZEICHEN, suche_a
suche_a, BLANK -> nicht_bewegen, BLANK, suche_a // kein a gefunden, Zykle unendlich

Analog für b.

Das Finden des Anfangs ist ähnlich, überschreibe das erste Zeichen des Paares direkt mit einem Blank, wenn du in den Suche-Zustand wechselst.
Dann musst du für das Zurücklaufen immer nur nach links gehen, bis du zum ersten Blank kommst. Dann bist du am Anfang des "Restwortes" und bereit für den nächsten Durchlauf.


PS: Wie kommt man denn mal an eine günstige Turingmaschine, bei meiner alten hat sich das Band verheddert

[Angel4585]

ich hab so ne aufgabe so gelöst indem ich zuerst die a's und die b's sortiert hab, also links alle a's und rechts alle b's. danach hab ich dann immer vorne ein a und hinten ein b gelöscht bis links keine a's oder rechts keine b's mehr waren. wenn dann noch a's oder b's übrig sind ist es nicht die gleiche anzahl.

edit: wegen dem sortieren: die aufgabe davor war, ich sollte feststellen ob in einem wort {a*b*} gleichviele a's und b's sind, ich hab dann in der nächsten aufgabe sortiert und auf die erste maschine verwiesen.