Subversion Repositories programming

#!/usr/bin/env python

# Copyright: Ira W. Snyder

# Start Date: 2005-10-08

# End Date:

# License: Public Domain

#

# Changelog Follows:

# - 2005-10-16

# - Implemented the nfa class. It's mostly complete at this point.

# - E() function works for circular loops now.

# - Made the nfa.__next_states() function always return a valid reference

#   to a list in the dictionary. This means you should NEVER use

#   self.trans_func[(state, letter)] in code anywhere now :)

# - Final states are now checked for validity.

#

################################################################################

# IMPORTANT NOTES

################################################################################

################################################################################

import sys, string

class nfa:

    """Implements a Non-Deterministic Finite Automaton"""

    def __init__(self):

        self.trans_func = {}

        self.num_states = 0

        self.final_states = []

        self.initial_state = 0

    def __state_in_range(self, state):

        """Check if a given state is in the acceptable range"""

        try:

            temp = int(state)

        except (TypeError, ValueError):

            return False

        if temp >= 0 and temp < self.num_states:

            return True

        return False

    def __input_num_states(self):

        """Get the number of states this automaton will have"""

        done = False

        while not done:

            num_states = raw_input('How many states in this automaton: ')

            try:

                self.num_states = int(num_states)

                done = True

            except (TypeError, ValueError):

                print 'Bad input, not an integer, try again'

                print

    def __input_final_states(self):

        """Get final states for this automaton"""

        print 'Enter final states on one line, seperated by spaces'

        done = False

        while not done:

            final_states = raw_input('Final states: ')

            bad_data = False

            for i in final_states.split():

                if not self.__state_in_range(i):

                    print 'State %s out of range. All input discarded.' % (i, )

                    print 'Try again please'

                    print

                    bad_data = True

                    break

            # if we left the for loop with bad data

            if bad_data:

                continue

            # all data is good

            for i in final_states.split():

                if self.__state_in_range(i):

                    self.final_states.append(int(i))

            done = True

    def __input_all_edges(self):

        """Read all of the edges for this automaton"""

        print 'Edges take the form "from HERE, by LETTER, to THERE"'

        print 'Enter something like: "1 a 1" to represent the following'

        print 'from q1, by a, go to q1'

        print

        print 'Conditions:'

        print '1. Blank line to end'

        print '2. ^ is the empty string'

        done = False

        while not done:

            edge = raw_input('Edge: ')

            if len(edge) == 0:

                done = True

                continue

            if len(edge.split()) != 3:

                print 'Bad edge entered'

                print

                continue

            (cur_st, letter, next_st) = edge.split()

            # Make sure the states entered are in range

            if self.__state_in_range(cur_st) and self.__state_in_range(next_st):

                new_state = False

                cur_st = int(cur_st)

                next_st = int(next_st)

                # Add the state to the list if it's not there already

                if next_st not in self.__next_states(cur_st, letter):

                    self.__next_states(cur_st, letter).append(next_st)

            else:

                print 'Invalid current or next state entered'

                print

                continue

    def __input_automaton(self):

        """Read this entire automaton's input"""

        self.__input_num_states()

        self.__input_final_states()

        self.__input_all_edges()

    def main_menu(self):

        #NOTE: All of this code is not what it's supposed to be.

        #      It is for TESTING ONLY.

        #

        #TODO: Generate a menu :)

        self.__input_automaton()

        print self.trans_func

        print self.num_states

        print self.final_states

        print self.initial_state

        print

        for i in range(self.num_states):

            print 'E(%d): %s' % (i, self.__E(i))

    def __next_states(self, state, letter):

        """Return the next states for the key (state, letter)"""

        try:

            next = self.trans_func[(state, letter)]

        except KeyError:

            # Create a new empty list for this state if it doesn't exist yet

            next = self.trans_func[(state, letter)] = []

        if letter == '^' and state not in next:

            next.append(state)

        return next

    def __E(self, state, storage=None, visited=None):

        """Calculate E(state) and return it. This handles circular E()

        calculations."""

        # Work around weird mutable default argument stuff

        if storage is None:

            storage = []

        # Work around weird mutable default argument stuff

        if visited is None:

            visited = []

        # Find all of the direct next states that we can get to by

        # the empty string, and append anything that is not already there

        for i in self.__next_states(state, '^'):

            if i not in storage:

                storage.append(i)

        # Visit everything in storage that has not been visited already

        for i in storage:

            if i not in visited:

                visited.append(i)

                temp = self.__E(i, storage, visited)

                # Avoid duplicating things in storage

                for j in temp:

                    if j not in storage:

                        storage.append(j)

        return storage

    def __unique_sort(self, li):

        """Make sure everything in a list is unique, and then sort it"""

        newlist = []

        for i in li:

            if i not in newlist:

                newlist.append(i)

        newlist.sort()

        return newlist

    def __generate_dfa_table(self):

        # get the list of all letters

        possible_letters = []

        for (state, letter) in self.trans_func.keys():

            if letter not in possible_letters:

                possible_letters.append(letter)

        # DFA_TABLE STRUCTURE

        #

        # [ [Final, DFA_State_Number, [States_in_NFA], letter_1, letter_2, ..., letter_n]

        #   [Final, DFA_State_Number, [States_in_NFA], letter_1, letter_2, ..., letter_n]

        #   [Final, DFA_State_Number, [States_in_NFA], letter_1, letter_2, ..., letter_n] ]

        #

        dfa_table = []

        # find the first state's definition

        def_in_nfa = self.__E(0)

        is_final = False

        temp_record = []

        # find out if we're final

        for i in def_in_nfa:

            if i in self.final_states:

                is_final = True

                break

        temp_record.append(is_final)

        temp_record.append(len(dfa_table))

        temp_record.append(def_in_nfa)

        # find out where we can go by each letter

        for l in possible_letters:

            where_to_go = []

            for s in def_in_nfa:

                where_to_go.extend(self.__next_states(s, l))

            where_to_go = self.__unique_sort(where_to_go)

            create_new_state = True

            for s in dfa_table:

                if s[2] == where_to_go:

                    temp_record.append(s[1])

                    create_new_state = False

                    break

            if create_new_state:

                # recurse???

                pass

################################################################################

# NEW STUFF IS AFTER THIS

################################################################################

        temp_record = [None for n in range(len(possible_letters) + 3)]

        # start at initial state

        # generate E(initial_state)

        # find out if we are a final state (based on E() )

        # name the state (starting at 0)

        #

    def output_dfa(self):

        #stuff here

        pass

if __name__ == '__main__':

    automaton = nfa()

    automaton.main_menu()