Turingmaschinen-Simulator

Das auf dieser Seite beschriebene Programm ist ein einfacher Simulator für Turingmaschinen. Mit ihm ist es möglich, eine Turingmaschine auf einzelne Wörter anzusetzen und im Einzelschittmodus abzuarbeiten sowie sich die von der Turingmaschine erkannte Sprache (mit Einschränkungen) aufzählen zu lassen. Das Programm ist Public-Domain. Sie können sich hier das Quellprogramm, diverse Executables sowie die weiter unten vorgestellte Beispielturingmaschine holen: Der Aufruf erfolgt mittels
turing aibjck.tm
wobei anstelle von aibjck.tm natürlich auch jede andere Turingmaschinen-Datei stehen kann. Nach dem Laden der Turingmaschine und ihrer Ausgabe, die zu Kontrollzwecken erfolgt, erscheint ein kleines Menü, von dem aus Sie mit der Turingmaschine experimentieren können.

Syntax der Turingmaschinen-Dateien

Die Syntax der Turingmaschinen-Dateien ist sehr einfach:
Turingmaschine ::=
    { Kommentarzeile }
    Menge der Eingabezeichen
    Menge der Zustände
    Menge der Bandsymbole (ohne \lambda)
    Startzustand
    Menge der Endzustände
    { Produktionen }
Alle am Dateianfang unmittelbar aufeinanderfolgenden und mit '#' beginnenden Zeilen werden als Kommentarzeilen erkannt.

Sowohl Bandsymbole als auch Zustände werden durch einzelne Zeichen von ASCII #33 ('!') bis ASCII #126 ('~') dargestellt, das Blankzeichen \lambda durch ' ' und Mengen durch einfache Hintereinanderschreibung der entsprechenden Zeichen.

Das Ganze soll an einem Beispiel veranschaulicht werden. Die Turingmaschine

T = (\{a,b,c\}, \{z_0,\ldots,z_{11}\}, \{a,b,c,X,\lambda\}, f, z_0, \{z_7\})
mit der Turingtafel
f a b c X \lambda
z0 (z8,\lambda,R) (z2,\lambda,R)   (z1,\lambda,R)  
z1   (z2,\lambda,R)   (z1,\lambda,R)  
z2   (z2,b,R) (z2,c,R)   (z3,\lambda,L)
z3     (z4,\lambda,L)    
z4   (z4,b,L) (z4,c,L)   (z5,\lambda,R)
z5   (z2,\lambda,R) (z6,\lambda,R)    
z6     (z6,\lambda,R)   (z7,\lambda,L)
z7          
z8 (z8,a,R) (z9,X,R)   (z8,X,R)  
z9   (z9,b,R) (z9,c,R)   (z10,\lambda,L)
z10     (z11,\lambda,L)    
z11 (z11,a,L) (z11,b,L) (z11,c,L) (z11,X,L) (z0,\lambda,R)
erkennt die Sprache
L = \{a^i b^j c^k \;|\; 0\leq i
Die entsprechende Turingmaschinen-Datei aibjck.tm sieht dann so aus: 
# Diese Turingmaschine erkennt die Sprache
# L = {a^i b^j c^k | 0<=i<j<k}.

abc 0123456789AB abcX 0 7
0a8 R   0b2 R           0X1 R
        1b2 R           1X1 R
        2b2bR   2c2cR           2 3 L
                3c4 L
        4b4bL   4c4cL           4 5 R
        5b2 R   5c6 R
                6c6 R           6 7 L
8a8aR   8b9XR           8X8XR
        9b9bR   9c9cR           9 A L
                AcB L
BaBaL   BbBbL   BcBcL   BXBXL   B 0 R
Außer L (links) und R (rechts) sind noch die Kopfbewegungen N bzw. O (keine Bewegung) sowie S (stop) zugelassen.

Das Programm ist sehr einfach gehalten und nimmt keine aufwendigen Syntax-Checks vor. Im Falle unkorrekter Turingmaschinen-Dateien wird daher in aller Regel keine Fehlermeldung ausgegeben. Bitte beachten Sie auch, daß Kommentarzeilen nur am Anfang angegeben werden können und unmittelbar aufeinanderfolgen müssen. Die erste Zeile in der Datei, die nicht mit einem '#' beginnt, und sei es auch nur eine Leerzeile, leitet bereits die eigentliche Maschinenbeschreibung ein.

Falls Sie Fragen, Kritik oder Anregungen haben, so wenden Sie sich bitte an Andreas Jung.

Andreas Jung, ajung@informatik.uni-rostock.de, 1067 hits