Subversion Repositories programming

Rev

Rev 137 | Rev 140 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 137 Rev 138
Line 23... Line 23...
23 
 
 23 
 
24 
class nfa:
 24 
class nfa:
25 
    """Implements a Non-Deterministic Finite Automaton"""
 25 
    """Implements a Non-Deterministic Finite Automaton"""
26 
 
 26 
 
27 
    def __init__(self):
 27 
    def __init__(self):
- 
 
 28 
        self.__clear()
- 
 
 29 
 
- 
 
 30 
    def __clear(self):
28 
        self.trans_func = {}
 31 
        self.trans_func = {}
29 
        self.num_states = 0
 32 
        self.num_states = 0
30 
        self.final_states = []
 33 
        self.final_states = []
31 
        self.initial_state = 0
 34 
        self.initial_state = 0
32 
        self.possible_letters = []
 35 
        self.possible_letters = []
Line 49... Line 52...
49 
        """Get the number of states this automaton will have"""
 52 
        """Get the number of states this automaton will have"""
50 
 
 53 
 
51 
        done = False
 54 
        done = False
52 
        while not done:
 55 
        while not done:
53 
            num_states = raw_input('How many states in this automaton: ')
 56 
            num_states = raw_input('How many states in this automaton: ')
- 
 
 57 
            print
54 
 
 58 
 
55 
            try:
 59 
            try:
56 
                self.num_states = int(num_states)
 60 
                self.num_states = int(num_states)
57 
                done = True
 61 
                done = True
58 
            except (TypeError, ValueError):
 62 
            except (TypeError, ValueError):
Line 65... Line 69...
65 
        print 'Enter final states on one line, seperated by spaces'
 69 
        print 'Enter final states on one line, seperated by spaces'
66 
 
 70 
 
67 
        done = False
 71 
        done = False
68 
        while not done:
 72 
        while not done:
69 
            final_states = raw_input('Final states: ')
 73 
            final_states = raw_input('Final states: ')
- 
 
 74 
            print
70 
 
 75 
 
71 
            bad_data = False
 76 
            bad_data = False
72 
            for i in final_states.split():
 77 
            for i in final_states.split():
73 
                if not self.__state_in_range(i):
 78 
                if not self.__state_in_range(i):
74 
                    print 'State %s out of range. All input discarded.' % (i, )
 79 
                    print 'State %s out of range. All input discarded.' % (i, )
Line 96... Line 101...
96 
        print 'from q1, by a, go to q1'
 101 
        print 'from q1, by a, go to q1'
97 
        print
 102 
        print
98 
        print 'Conditions:'
 103 
        print 'Conditions:'
99 
        print '1. Blank line to end'
 104 
        print '1. Blank line to end'
100 
        print '2. ^ is the empty string'
 105 
        print '2. ^ is the empty string'
- 
 
 106 
        print
101 
 
 107 
 
102 
        done = False
 108 
        done = False
103 
        while not done:
 109 
        while not done:
104 
            edge = raw_input('Edge: ')
 110 
            edge = raw_input('Edge: ')
105 
 
 111 
 
Line 139... Line 145...
139 
        # Make sure to visit all '^' states (to make printing easier, later)
 145 
        # Make sure to visit all '^' states (to make printing easier, later)
140 
        for i in range(self.num_states):
 146 
        for i in range(self.num_states):
141 
            self.__E(i)
 147 
            self.__E(i)
142 
 
 148 
 
143 
    def main_menu(self):
 149 
    def main_menu(self):
144 
        #NOTE: All of this code is not what it's supposed to be.
 - 
 
145 
        #      It is for TESTING ONLY.
 - 
 
146 
        #
 150 
        done = False
147 
        #TODO: Generate a menu :)
 151 
        automaton_entered = False
148 
 
 152 
 
- 
 
 153 
        while not done:
- 
 
 154 
            print 'Menu:'
- 
 
 155 
            print '========================================'
- 
 
 156 
            print '1. Enter an NFA'
- 
 
 157 
            print '2. Output corresponding DFA'
- 
 
 158 
            print '3. Quit'
- 
 
 159 
            print
- 
 
 160 
            s = raw_input('Choice >>> ')
- 
 
 161 
            print
- 
 
 162 
 
- 
 
 163 
            if s == '1':
- 
 
 164 
                self.__clear()
149 
        self.__input_automaton()
 165 
                self.__input_automaton()
- 
 
 166 
                automaton_entered = True
- 
 
 167 
                print
- 
 
 168 
            elif s == '2':
- 
 
 169 
                if automaton_entered:
- 
 
 170 
                    self.__output_dfa()
- 
 
 171 
                else:
- 
 
 172 
                    print 'Enter a NFA first'
- 
 
 173 
                print
- 
 
 174 
            elif s == '3':
- 
 
 175 
                done = True
- 
 
 176 
            else:
- 
 
 177 
                print 'Bad Selection'
- 
 
 178 
                print
150 
 
 179 
 
151 
        print
 180 
    def __output_dfa(self):
152 
        print
 181 
        print
153 
        print 'Initial State: %s' % (0, )
 182 
        print 'Initial State: %s' % (0, )
154 
        print
 183 
        print
155 
        self.__generate_dfa_table()
 184 
        self.__generate_dfa_table()
156 
        self.__print_dfa_table()
 185 
        self.__print_dfa_table()
- 
 
 186 
        print
157 
 
 187 
 
158 
    def __print_dfa_table(self):
 188 
    def __print_dfa_table(self):
159 
        header1 = '%-8s%-8s%-20s' % ('Final', 'Number', 'NFA Equiv')
 189 
        #header1 = '%-8s%-8s%-20s' % ('Final', 'Number', 'NFA Equiv')
- 
 
 190 
        header1 = '%-8s%-8s' % ('Final', 'State #')
160 
        header2 = ''
 191 
        header2 = ''
161 
 
 192 
 
162 
        for l in self.possible_letters:
 193 
        for l in self.possible_letters:
163 
            header2 = '%s%-4s' % (header2, l)
 194 
            header2 = '%s%-4s' % (header2, l)
164 
 
 195 
 
165 
        heading = '%s %s' % (header1, header2)
 196 
        heading = '%s %s' % (header1, header2)
166 
        hdr_line = ''
 197 
        hdr_line = ''
167
198 
 
168 
        for i in range(len(heading)):
 199 
        for i in range(len(heading)):
169 
            hdr_line = '%s-' % (hdr_line, )
 200 
            hdr_line = '%s-' % (hdr_line, )
170 
 
 201 
 
171 
        print heading
 202 
        print heading
172 
        print hdr_line
 203 
        print hdr_line
173 
 
 204 
 
174 
        for rec in self.dfa_table:
 205 
        for rec in self.dfa_table:
175 
            line1 = '%-8s%-8s%-20s' % (rec[0], rec[1], rec[2])
 206 
            #line1 = '%-8s%-8s%-20s' % (rec[0], rec[1], rec[2])
- 
 
 207 
            line1 = '%-8s%-8s' % (rec[0], rec[1])
176 
            line2 = ''
 208 
            line2 = ''
177
209 
 
178 
            for l in range(len(self.possible_letters)):
 210 
            for l in range(len(self.possible_letters)):
179 
                line2 = '%s%-4s' % (line2, rec[l+3])
 211 
                line2 = '%s%-4s' % (line2, rec[l+3])
180 
 
 212 
 
181 
            print '%s %s' % (line1, line2)
 213 
            print '%s %s' % (line1, line2)
182 
 
 214 
 
Line 277... Line 309...
277 
 
 309 
 
278 
    def __get_temp_record(self, num_letters):
 310 
    def __get_temp_record(self, num_letters):
279 
        blank = None
 311 
        blank = None
280 
        return [blank for i in range(num_letters + 3)]
 312 
        return [blank for i in range(num_letters + 3)]
281 
 
 313 
 
282 
    def __generate_dfa_table(self):
 314 
    def __get_possible_letters(self):
283 
 
 315
284 
        # get the list of all letters
 316 
        # get the list of all letters
285 
        possible_letters = []
 317 
        possible_letters = []
286 
 
 318 
 
287 
        for (state, letter) in self.trans_func.keys():
 319 
        for (state, letter) in self.trans_func.keys():
288 
            if letter not in possible_letters and letter != '^':
 320 
            if letter not in possible_letters and letter != '^':
289 
                possible_letters.append(letter)
 321 
                possible_letters.append(letter)
290 
 
 322 
 
- 
 
 323 
        possible_letters = self.__unique_sort(possible_letters)
291 
        self.possible_letters = possible_letters
 324 
        self.possible_letters = possible_letters
- 
 
 325
- 
 
 326 
    def __generate_dfa_table(self):
- 
 
 327 
 
- 
 
 328 
        # get all the possible letters
- 
 
 329 
        self.__get_possible_letters()
292 
 
 330 
 
293 
        #prime the dfa table
 331 
        # prime the dfa table
294 
        self.make_basic_record(self.__E(0))
 332 
        self.make_basic_record(self.__E(0))
295 
 
 333 
 
296 
        while self.find_unresolved_letter() != (-1, -1): #loop until we've resolved everything
 334 
        while self.find_unresolved_letter() != (-1, -1): #loop until we've resolved everything
297 
            (record, letter_pos) = self.find_unresolved_letter()
 335 
            (record, letter_pos) = self.find_unresolved_letter()
298 
            self.resolve_letter(record, letter_pos)
 336 
            self.resolve_letter(record, letter_pos)