Turing-Machine Simulator

gistfile2.txt

turing_machine.py

#!/usr/bin/env python

class Tape(object):
    def __init__(self, string):
        self.string = string
        self.index = 0

    def L(self):
        if self.index > 0:
            self.index = self.index - 1

    def R(self):
        self.index = self.index + 1
        if self.index >= len(self.string):
            self.string = self.string + "_"

    def READ(self):
        if self.index >= len(self.string):
            return '_'
        else:
            return self.string[self.index]

    def WRITE(self, char):
        self.string = self.string[:self.index] + char + self.string[self.index+1:]

class TM(object):
    def __init__(self, delta, start, accept, reject):
        self.delta = delta
        self.state = self.start = start
        self.accept = accept
        self.reject = reject
        self.dump = False
        self.tape = None
        self.result = False

    def does_accept(self, string):
        self.tape = Tape(string)
        self.state = self.start
        if self.dump: self.dumptape()
        self.do_transition()
        return self.result

    def dumptape(self):
        print self.tape.string[:self.tape.index] + "'" + self.state + "'" + self.tape.string[self.tape.index:]

    def error(self):
        raise Exception("invalid sequence.")

    def do_transition(self):
        while True:
            try:
                result = self.delta[self.state][self.tape.READ()]
            except KeyError:
                self.error()

            if len(result) == 3: # with write
                self.state, char, direction = result
                self.tape.WRITE(char)
            else:
                self.state, direction = result

            getattr(self.tape, direction, self.error)()

            if self.dump: self.dumptape()

            if self.state == self.accept:
                self.result = True
                break
            elif self.state == self.reject:
                self.result = False
                break