turinginterpreter/Turingmachine.py

201 lines
6.6 KiB
Python
Executable File

#!/usr/bin/env python3
import numpy as np
import sys
import time
# Bezeichnungen:
# delta = Zustandsübergangsfunktion: eine Liste von Tupeln im Format:
# (aktuellerZustand, aktuelleZeichen[Tupel], nächsterZustand, zuSchreibendeZeichen[Tupel], orientation[Tupel])
# q0 = Startzustand
# F = Menge der Endzustände
#ein paar konstanten:
GO_LEFT = -1
GO_NOWHERE = 0
GO_RIGHT = 1
#zur vereinfachung: konstanten für indices in delta:
DELTA_CURRENT_STATE = 0
DELTA_CURRENT_CHARS = 1
DELTA_NEXT_STATE = 2
DELTA_NEXT_CHARS = 3
DELTA_ORIENTATIONS = 4
#Konstanten für die Ausgabe:
CURSOR_UP_ONE = '\x1b[1A'
ERASE_LINE = '\x1b[2K'
#hilfsfunktionen für die ausgabe:
def eraseLines(n):
for i in range(n):
print(CURSOR_UP_ONE + ERASE_LINE, end = "")
#und die eigentliche Turingmaschine:
class Turingmachine(object):
def __init__(self,delta, q0, F, n, inputStr):
self.delta = delta
self.q0 = q0
self.F = F
self.n = n
#zur internen Verwaltung der Turinmaschine brauchen wir folgendes:
self.stripes = []
self.positions = []
self.steps = 0 #counting the steps
for i in range(n):
self.stripes.append(['$'])
self.positions.append(0)
#schreibe unsere Eingabe auf das erste Band:
for c in inputStr:
self.stripes[0].append(c)
self.currentQ = q0
self.error = False
self.isInFinalState = False
self.firstPrint = True
# Lese char unter dem i-ten Lesekopf:
def readChar(self,i):
#erweitere Band, falls notwendig:
if len(self.stripes[i]) <= self.positions[i]:
self.stripes[i].append('_')
#und Zeichen zurückgeben:
return self.stripes[i][self.positions[i]]
# Schreibe char unter dem i-ten Lesekopf:
def writeChar(self,i, char):
#erweitere Band, falls notwendig:
if len(self.stripes[i]) <= self.positions[i]:
self.stripes[i].append('_')
#und setze Zeichen:
self.stripes[i][self.positions[i]] = char
#bewege den Lese-/Schreibkopf
def move(self, i, orientation):
self.positions[i] += orientation
#führe einen Zustandsübergang aus: (gibt true bei erfolg zurück, sonst false)
def runDelta(self):
#durchlaufe alle Übergänge in Delta
for d in self.delta:
#suche nach Übergängen für unseren Zustand:
if d[DELTA_CURRENT_STATE] == self.currentQ:
#prüfe Einganszeichen:
qInputChars = d[DELTA_CURRENT_CHARS]
isInputOK = True
for i in range(self.n):
if not ((qInputChars[i] == self.readChar(i)) or (qInputChars[i] == '*')):
#eingangszeichen stimmen nicht überein!
isInputOK = False
if isInputOK:
#jetzt haben wir den richtigen zustandsübergang gefunden!
qNextChars = d[DELTA_NEXT_CHARS]
qOrientations = d[DELTA_ORIENTATIONS]
for i in range(self.n):
#schreibe Zeichen:
if qNextChars[i] != '*':
self.writeChar(i, qNextChars[i])
#Bewege Lese-/Schreibkopf
self.move(i, qOrientations[i])
#prüfe auf underflows:
for j in range(self.n):
if self.positions[j] < 0:
return False
#setze nächsten Zustand:
self.currentQ = d[DELTA_NEXT_STATE]
self.steps+=1
#fertig!
return True
#wenn wir bis hierhin kommen, haben wir keinen Übergang gefunden!
return False
# mache einen einzelnen Schritt mit der Turing Maschine (gibt true bei erfolg zurück, sonst false)
def step(self):
#führe den Schritt nuraus, wenn wir noch nicht im Endzustand sind:
if not self.isInFinalState:
self.error = not self.runDelta()
#schaue, ob wir in einem Endzustand sind:
self.isInFinalState = (self.currentQ in self.F)
return self.error
return True
def printMachine(self):
if not self.firstPrint:
#Lösche voherige Ausgabe:
eraseLines(2 * self.n + 1)
self.firstPrint = False
#geben bänder aus:
for i in range(self.n):
print("[",end="")
for c in self.stripes[i]:
print(c,end = "")
print("]")
#drucke lese-/Schreibkopf
print (" " * (self.positions[i] +1) + "^")
#und gebe allgemeine Infos aus:
print("step: " + str(self.steps) + "\t currentState: " + str(self.currentQ))
#run the machine until it gets to a final state:
def run(self, delayInSeconds):
while not self.isInFinalState:
self.step()
self.printMachine()
if self.error:
print("ERROR! Please check your Turing Program") #TODO: aussagekräftigere Fehlermeldung?
break
time.sleep(delayInSeconds)
if not self.error:
self.printMachine()
print("Maschine terminatet!")
if __name__ == "__main__":
#Blatt13/Aufgabe01 zum testen:
F = ['finalState']
d = [('start',"$$$$",'init',"$$$$",(1,1,1,1)),
('init',"****",'a',"*!!!",(0,1,1,1)),
('a',"a***",'a',"aa**",(1,1,0,0)),
('a',"b***",'b',"b***",(0,0,0,0)),
('b',"b***",'b',"b*b*",(1,0,1,0)),
('b',"c***",'c',"c***",(0,0,0,0)),
('c',"c***",'c',"c**c",(1,0,0,1)),
('c',"_***",'counting',"_***",(-1,-1,-1,-1)),
('counting',"*abc",'counting',"*abc",(0,-1,-1,-1)),
('counting',"*!**",'checkCounter',"*!**",(0,0,0,0)),
('counting',"**!*",'checkCounter',"**!*",(0,0,0,0)),
('counting',"***!",'checkCounter',"***!",(0,0,0,0)),
('checkCounter','*!!!','wordAccepted','*!!!',(0,0,0,0)),
('checkCounter','****','wordNotAccepted','****',(0,0,0,0)),
('wordAccepted','$***','write1','$***',(1,0,0,0)),
('wordAccepted','****','wordAccepted','_***',(-1,0,0,0)),
('wordNotAccepted','$***','write0','$***',(1,0,0,0)),
('wordNotAccepted','****','wordNotAccepted','_***',(-1,0,0,0)),
('write0','****','finalState','0***',(0,0,0,0)),
('write1','****','finalState','1***',(0,0,0,0))
]
tm = Turingmachine(d, 'start', F, 4, "aaaaaaaaabbbbbbbbbccccccccc")
tm.run(0.15)