- Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathState.py
More file actions
Latest commit
81 lines (74 loc) · 3.46 KB
/
Copy pathState.py
File metadata and controls
81 lines (74 loc) · 3.46 KB
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
classState(object):
def__init__(self, state_type, next_state=None):
"""If state_type='Start', then a next_state must be provided."""
ifstate_typenotin ('Accept', 'Push', 'Pop', 'Read', 'Start'):
raiseSystemExit(state_type+" is not a valid State type!")
ifstate_type=='Start'andnotnext_state:
raiseSystemExit("Start states must be provided a next_state!")
self.state_type=state_type
self.transitions=list()
self.next_state=next_state
defadd_transition(self, next_state, character=None):
"""Adds a transition to the list of the state's acceptable
transitions. A transition consists of at least a next state, and a
character depending on the type of the state."""
transition= {'char': character, 'next': next_state}
self.transitions.append(transition)
defget_next_state(self, character=None):
"""Retrieves the next state that the PDA should go to, based on the
current state's type, and an input from either the tape or stack."""
ifself.state_type=="Start":
returnself.next_state
ifself.state_type=="Read":
ifcharacter=="":
returnself.transitions[0]['next']
fortransitioninself.transitions:
iftransition['char'] ==character:
returntransition['next']
ifself.state_type=="Push":
returnself.transitions[0]['next']
ifself.state_type=="Pop":
fortransitioninself.transitions:
iftransition['char'] ==character:
returntransition['next']
defaction(self, tape, stack, verbose=False):
"""If state_type is Read, Push, or Pop, the respective action is taken
and the get_next_state() retrieves the next state in the PDA. The
action() function of the next state is then called.
If state_type is Start, next state's action() function is called.
If state_type is Accept, the state simply prints a message."""
ifverbose:
print("TAPE: ", tape)
print("STACK: ", stack)
try:
ifself.state_type=="Start":
ifverbose:
print("START -> next_state")
self.get_next_state().action(tape, stack, verbose)
elifself.state_type=="Read":
ifverbose:
print("READ "+tape[0] +"")
self.get_next_state(character=tape[0]).action(tape[1:], stack, verbose)
elifself.state_type=="Push":
char=self.transitions[0]['char']
stack.append(char)
ifverbose:
print("PUSH "+char+"")
self.get_next_state().action(tape, stack, verbose)
elifself.state_type=="Pop":
char=stack.pop()
ifverbose:
print("POP "+char+"")
self.get_next_state(character=char).action(tape, stack, verbose)
elifself.state_type=="Accept":
print("Tape accepted!")
ifverbose:
print("FINAL TAPE: ", tape)
print("FINAL STACK: ", stack)
else:
pass
except:
print("Tape NOT accepted!")
ifverbose:
print("FINAL TAPE: ", tape)
print("FINAL STACK: ", stack)