| 130 |
ira |
1 |
#!/usr/bin/env python
|
|
|
2 |
# Copyright: Ira W. Snyder
|
|
|
3 |
# Start Date: 2005-10-08
|
|
|
4 |
# End Date:
|
|
|
5 |
# License: Public Domain
|
|
|
6 |
#
|
|
|
7 |
# Changelog Follows:
|
|
|
8 |
#
|
|
|
9 |
|
|
|
10 |
################################################################################
|
|
|
11 |
# IMPORTANT NOTES
|
|
|
12 |
################################################################################
|
|
|
13 |
################################################################################
|
|
|
14 |
|
|
|
15 |
import sys, string
|
|
|
16 |
|
|
|
17 |
class nfa:
|
|
|
18 |
"""Implements a Non-Deterministic Finite Automaton"""
|
|
|
19 |
|
|
|
20 |
def __init__(self):
|
|
|
21 |
self.trans_func = {}
|
|
|
22 |
self.num_states = 0
|
|
|
23 |
self.final_states = []
|
|
|
24 |
self.initial_state = 0
|
|
|
25 |
|
|
|
26 |
def __state_in_range(self, state):
|
|
|
27 |
"""Check if a given state is in the acceptable range"""
|
|
|
28 |
|
|
|
29 |
try:
|
|
|
30 |
temp = int(state)
|
|
|
31 |
except (TypeError, ValueError):
|
|
|
32 |
return False
|
|
|
33 |
|
|
|
34 |
if temp >= 0 and temp < self.num_states:
|
|
|
35 |
return True
|
|
|
36 |
|
|
|
37 |
return False
|
|
|
38 |
|
|
|
39 |
def __input_num_states(self):
|
|
|
40 |
"""Get the number of states this automaton will have"""
|
|
|
41 |
|
|
|
42 |
done = False
|
|
|
43 |
while not done:
|
|
|
44 |
num_states = raw_input('How many states in this automaton: ')
|
|
|
45 |
|
|
|
46 |
try:
|
|
|
47 |
self.num_states = int(num_states)
|
|
|
48 |
done = True
|
|
|
49 |
except (TypeError, ValueError):
|
|
|
50 |
print 'Bad input, not an integer, try again'
|
|
|
51 |
print
|
|
|
52 |
|
|
|
53 |
def __input_final_states(self):
|
|
|
54 |
"""Get final states for this automaton"""
|
|
|
55 |
|
|
|
56 |
print 'Enter final states on one line, seperated by spaces'
|
|
|
57 |
|
|
|
58 |
done = False
|
|
|
59 |
while not done:
|
|
|
60 |
final_states = raw_input('Final states: ')
|
|
|
61 |
|
|
|
62 |
bad_data = False
|
|
|
63 |
for i in final_states.split():
|
|
|
64 |
if not self.__state_in_range(i):
|
|
|
65 |
print 'State %s out of range. All input discarded.' % (i, )
|
|
|
66 |
print 'Try again please'
|
|
|
67 |
print
|
|
|
68 |
bad_data = True
|
|
|
69 |
break
|
|
|
70 |
|
|
|
71 |
# if we left the for loop with bad data
|
|
|
72 |
if bad_data:
|
|
|
73 |
continue
|
|
|
74 |
|
|
|
75 |
# all data is good
|
|
|
76 |
for i in final_states.split():
|
|
|
77 |
self.final_states.append(int(i))
|
|
|
78 |
|
|
|
79 |
done = True
|
|
|
80 |
|
|
|
81 |
def __input_all_edges(self):
|
|
|
82 |
"""Read all of the edges for this automaton"""
|
|
|
83 |
|
|
|
84 |
print 'Edges take the form "from HERE, by LETTER, to THERE"'
|
|
|
85 |
print 'Enter something like: "1 a 1" to represent the following'
|
|
|
86 |
print 'from q1, by a, go to q1'
|
|
|
87 |
print
|
|
|
88 |
print 'Conditions:'
|
|
|
89 |
print '1. Blank line to end'
|
|
|
90 |
print '2. ^ is the empty string'
|
|
|
91 |
|
|
|
92 |
done = False
|
|
|
93 |
while not done:
|
|
|
94 |
edge = raw_input('Edge: ')
|
|
|
95 |
|
|
|
96 |
if len(edge) == 0:
|
|
|
97 |
done = True
|
|
|
98 |
continue
|
|
|
99 |
|
|
|
100 |
if len(edge.split()) != 3:
|
|
|
101 |
print 'Bad edge entered'
|
|
|
102 |
print
|
|
|
103 |
continue
|
|
|
104 |
|
|
|
105 |
(cur_st, letter, next_st) = edge.split()
|
|
|
106 |
|
|
|
107 |
if self.__state_in_range(cur_st) and self.__state_in_range(next_st):
|
|
|
108 |
new_state = False
|
|
|
109 |
|
|
|
110 |
try:
|
|
|
111 |
self.trans_func[(int(cur_st), letter)]
|
|
|
112 |
except KeyError:
|
|
|
113 |
new_state = True
|
|
|
114 |
|
|
|
115 |
if new_state:
|
|
|
116 |
self.trans_func[(int(cur_st), letter)] = [int(next_st)]
|
|
|
117 |
else:
|
|
|
118 |
self.trans_func[(int(cur_st), letter)].append(int(next_st))
|
|
|
119 |
|
|
|
120 |
else:
|
|
|
121 |
print 'Invalid current or next state entered'
|
|
|
122 |
print
|
|
|
123 |
continue
|
|
|
124 |
|
|
|
125 |
def __input_automaton(self):
|
|
|
126 |
"""Read this entire automaton's input"""
|
|
|
127 |
|
|
|
128 |
self.__input_num_states()
|
|
|
129 |
self.__input_final_states()
|
|
|
130 |
self.__input_all_edges()
|
|
|
131 |
|
|
|
132 |
def main_menu(self):
|
|
|
133 |
self.__input_automaton()
|
|
|
134 |
|
|
|
135 |
print self.trans_func
|
|
|
136 |
print self.num_states
|
|
|
137 |
print self.final_states
|
|
|
138 |
print self.initial_state
|
|
|
139 |
print 'E(0): %s' % (self.__E(0), )
|
|
|
140 |
print 'E(1): %s' % (self.__E(1), )
|
|
|
141 |
|
|
|
142 |
def __next_states(self, state, letter):
|
|
|
143 |
next = []
|
|
|
144 |
|
|
|
145 |
try:
|
|
|
146 |
next = self.trans_func[(state, letter)]
|
|
|
147 |
except KeyError:
|
|
|
148 |
pass
|
|
|
149 |
|
|
|
150 |
return next
|
|
|
151 |
|
|
|
152 |
def __E(self, state, storage=[], visited=[]):
|
|
|
153 |
|
|
|
154 |
# If nothing was inputted for the null string from this state
|
|
|
155 |
# return itself only (as a list)
|
|
|
156 |
if len(self.__next_states(state, '^')) == 0:
|
|
|
157 |
print 'stop rec: %s' % ([state], )
|
|
|
158 |
return [state]
|
|
|
159 |
|
|
|
160 |
for i in self.__next_states(state, '^'):
|
|
|
161 |
print 'next state: %s -- storage: %s -- visited: %s' % (i, storage, visited)
|
|
|
162 |
|
|
|
163 |
if i not in storage and i not in visited:
|
|
|
164 |
storage.append(state) #add yourself to the list
|
|
|
165 |
visited.append(i)
|
|
|
166 |
print 'making the call: (%s, %s, %s)' % (i, storage, visited)
|
|
|
167 |
storage.extend(self.__E(i, storage, visited))
|
|
|
168 |
|
|
|
169 |
return storage
|
|
|
170 |
|
|
|
171 |
def output_dfa(self):
|
|
|
172 |
#stuff here
|
|
|
173 |
pass
|
|
|
174 |
|
|
|
175 |
if __name__ == '__main__':
|
|
|
176 |
automaton = nfa()
|
|
|
177 |
automaton.main_menu()
|
|
|
178 |
|
|
|
179 |
|