-
Notifications
You must be signed in to change notification settings - Fork 0
/
machine.py
89 lines (82 loc) · 2.32 KB
/
machine.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import sys
debug = False
class Machine:
def __init__(self, program, tape=" "*600):
self.program = program
self.tape = [char for char in (tape+"$")]
self.head = 0
self.crash = False
self.halt = False
def run(self):
global debug
while not self.crash and not self.halt:
self.program.advance(self, self.tape[self.head])
if debug:
print(self.tape, self.head)
print(self.tape)
if self.crash:
print("CRASHED")
else:
print("HALTED")
def write(self, cell):
self.tape[self.head] = cell
def move(self, amt):
self.head += amt
class Transition:
def __init__(self, key, write, action, nextState):
self.key = key
self.write = write
self.action = action
self.nextState = nextState
class State:
def __init__(self, halt=False, name=""):
self.HALT = halt
self.name = name
self.transitions = {}
def addTransition(self, t):
self.transitions[t.key] = t
class Program:
def __init__(self, states=None):
self.state = 0
self.states = states or []
def add_state(self, state):
self.states.append(state)
def advance(self, machine, cell):
if cell not in self.states[self.state].transitions:
machine.crash = True
return
t = self.states[self.state].transitions[cell]
if debug:
print(self.state, t.nextState, cell)
machine.write(t.write)
machine.move(t.action)
self.state = t.nextState
if self.states[self.state].HALT:
machine.halt = True
if __name__ == "__main__":
state1 = State()
state1.addTransition(Transition('a', 'A', 1, 1))
state1.addTransition(Transition('$', '$', 1, 5))
state2 = State()
state2.addTransition(Transition('a', 'a', 1, 1))
state2.addTransition(Transition('B', 'B', 1, 1))
state2.addTransition(Transition('b', 'B', -1, 2))
state3 = State()
state3.addTransition(Transition('B', 'B', -1, 2))
state3.addTransition(Transition('a', 'a', -1, 3))
state3.addTransition(Transition('A', 'A', 1, 4))
state4 = State()
state4.addTransition(Transition('a', 'a', -1, 3))
state4.addTransition(Transition('A', 'A', 1, 0))
state5 = State()
state5.addTransition(Transition('B', 'B', 1, 4))
state5.addTransition(Transition('$', '$', 1, 5))
state6 = State(halt=True)
tape = "aabb"
if len(sys.argv) > 1:
tape = sys.argv[1]
if len(sys.argv) > 2 and sys.argv[2] == '-d':
debug = True
x = Program([state1, state2, state3, state4, state5, state6])
tm = Machine(x, tape)
tm.run()