Erstellen Sie eine Turing Maschine, die für eine beliebige Zeichenkette feststellt, ob sie aus n Nullen gefolgt von n Einsen besteht.


Eine korrekte Zeichenkette



Eine ungültige Zeichenketten

Ausgangslage

Die Zeichenkette ist vorne und hinten durch ein Doppelkreuz begrenzt. Der Lesekopf steht am Anfang ganz links auf dem Doppelkreuz.

Schlussbedingungen

Falls es sich bei der Eingabe um eine korrekte Zeichenkette handelt, soll die Turing Maschine auf dem leeren Band terminieren. Ist die Eingabe nicht korrekt, darf das Band am Schluss nicht leer sein.