Übergangstabelle einer Turingmaschine angeben.

Question

Gegeben  ist  eine  Folge,  die  aus  den  Ziffern 0 und 1besteht,  wobei  die  Elemente  jeweils  durch  Leerzeichen  getrennt  sind  und  die  Folge  mit # abgeschlossen  wird.  Die  Leerzeichen  sind  durch  die  korrek-ten  Vergleichsoperatoren <,= bzw.> zu  ersetzen,  das  Schlusszeichen  ist  zu  löschen.  Aus  der  Eingabe 0_1_1_0_0_1_0_0_1_#
soll beispielsweise die Zeichenfolge 0<1=1>0=0<1>0=0<1 erzeugt werden.

Geben Sie dazu das Eingabealphabet Σ und die Übergangstabelle an. Zu Beginn soll der Lese-Schreib-Kopf vor der ersten Ziffer stehen, am Ende hinter der letzten.

Answer 1

Am besten überlegst du dir eine Turing-Maschine und zeichnest sie im Zustandsdiagramm auf.

Dann kannst du die Tabelle einfacher machen, weil es übersichtlicher ist und einfach nur die Transitionen abgegangen werden müssen.

Es wird von der Vorgehensweise so funktionieren:

Lese die erste Zahl, für 0 gehe in Zweig A, für 1 in Zweig B.

Überspringe das _ Zeichen und lese die zweite Zahl. Für 0 gehst du in AC oder BC, für 1 gehst du in AD oder BD(Zweige)

Im Zweig:

AC ersetzt du _ mit =

BC ersetzt du _ mit >

AD ersetzt du _ mit <

BD ersetzt du _ mit =

Du siehst dass Zweig AC und BD der selbe sind. Nach jedem der letzten Zweige setzt du den Lesekopf ein Zeichen nach rechts und gehst in den Startzustand.

Bei Fragen gerne melden.