Subversion Repositories programming

#!/usr/bin/env python

# Copyright: Ira W. Snyder

# Start Date: 2005-10-08

# End Date: 2005-10-24

# 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.

#

# - 2005-10-19

# - Everything now works, with a menu even.

#

# - 2005-10-20

# - Added the check for <Python-2.3 compatibility.

# - Commented the source more.

#

# - 2005-10-22

# - Removed an unnecessary call in input_automaton()

#

# - 2005-10-24

# - Realized that I need to call E(states) after I find out where I'm going.

#   The program wasn't working at all before, now it is. See class notes from

#   2005-10-24 for some examples that weren't working.

# - Made 'True' and 'False' print correctly even if we are on pre-boolean

#   version of python.

# - Added a 'Verbose Mode' toggle to the menu. This makes the outputted DFA

#   table have more information: the NFA Equiv. State

# - It's ready to be turned in now :)

#

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

# IMPORTANT NOTES

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

# The DFA table format:

#

# [ [Final, 0, NFA_Equivalent, letter1, letter2, ..., lettern],

# [ [Final, 1, NFA_Equivalent, letter1, letter2, ..., lettern],

# [ [Final, 2, NFA_Equivalent, letter1, letter2, ..., lettern] ]

#

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

# The nfa.trans_func format:

#

# dict[(state, letter)] = [list, of, states]

#

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

# Check for <Python-2.3 compatibility (boolean values)

try:

  True, False

except NameError:

  (True, False) = (1, 0)

import sys, string

class nfa:

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

    def __init__(self):

        """Constructor for the nfa object"""

        self.__clear()

        self.verbose = False

    def __clear(self):

        """Clear all instance variables of the nfa class"""

        self.trans_func = {}

        self.num_states = 0

        self.final_states = []

        self.initial_state = 0

        self.possible_letters = []

        self.dfa_table = []

    def __state_in_range(self, state):

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

        # Check to make sure this can be converted to an int.

        # Return False if the conversion fails.

        try:

            temp = int(state)

        except (TypeError, ValueError):

            return False

        # Make sure this is a state in the range

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

            return True

        # We weren't in the correct range, so return False

        return False

    def __input_num_states(self):

        """Ask the user (nicely) for the number of states this automaton will have"""

        done = False

        while not done:

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

            print

            # Make sure we can convert the value successfully, then set

            # the num_states variable.

            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):

        """Ask the user for a list of final states for this automaton"""

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

        done = False

        while not done:

            final_states = raw_input('Final states: ')

            print

            # Check each value entered, one by one, and set bad_data if there

            # was a state out of the valid range

            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, start over.

            if bad_data:

                continue

            # All data is good, read the values into the final_states list.

            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):

        """Ask the user to input all of the edges for this automaton"""

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

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

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

        print

        print 'RULES:'

        print '------------------------------------------------------'

        print '1. Enter a blank line to stop reading edges'

        print '2. ^ is the empty string'

        print '3. Enter one letter at a time (no multi-letter states)'

        print

        # Read edges, one by one. Check them as they are entered.

        done = False

        while not done:

            edge = raw_input('Edge: ')

            # Check to see if we got a blank line

            if len(edge) == 0:

                done = True

                continue

            # If we didn't get exactly 3 arguments, try again

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

                print 'Bad edge entered.'

                print 'Exactly 3 arguments are required for a valid edge.'

                print

                continue

            # All checks appear fine, set a variable for each piece

            (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)    # convert to int

                next_st = int(next_st)  # convert to int

                # 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: # At least one state was not in range

                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):

        """Display the main menu for this automaton"""

        done = False

        automaton_entered = False

        while not done:

            print 'Menu:'

            print '========================================'

            print '1. Enter an NFA'

            print '2. Output corresponding DFA'

            print '3. %s Verbose Mode' % (self.verbose and 'Disable' or 'Enable', )

            print '4. Quit'

            print

            s = raw_input('Choice >>> ')

            print

            if s == '1':

                self.__clear()

                self.__input_automaton()

                automaton_entered = True

                print

            elif s == '2':

                if automaton_entered:

                    self.__output_dfa()

                else:

                    print 'Enter a NFA first'

                print

            elif s == '3':

                self.verbose = not self.verbose

                print 'Verbose Mode %s' % (self.verbose and 'Enabled' or 'Disabled', )

                print

            elif s == '4':

                done = True

            else:

                print 'Bad Selection'

                print

    def __output_dfa(self):

        """Generate and print the DFA that corresponds to the NFA entered"""

        print

        print 'Initial State: %s' % (0, )

        print

        self.__generate_dfa_table()

        self.__print_dfa_table()

        print

    def __print_dfa_table(self):

        """Print out a nicely spaced representation of the DFA's table"""

        if self.verbose:

            header1 = '%-8s%-8s%-20s' % ('Final', 'Number', 'NFA Equiv. State')

        else:

            header1 = '%-8s%-8s' % ('Final', 'State #')

        header2 = ''

        for l in self.possible_letters:

            header2 = '%s%-4s' % (header2, l)

        heading = '%s %s' % (header1, header2)

        hdr_line = ''

        for i in range(len(heading)):

            hdr_line = '%s-' % (hdr_line, )

        print heading

        print hdr_line

        for rec in self.dfa_table:

            if self.verbose:

                line1 = '%-8s%-8s%-20s' % (rec[0] and 'True' or 'False', rec[1], rec[2])

            else:

                line1 = '%-8s%-8s' % (rec[0] and 'True' or 'False', rec[1])

            line2 = ''

            for l in range(len(self.possible_letters)):

                line2 = '%s%-4s' % (line2, rec[l+3])

            print '%s %s' % (line1, line2)

    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)] = []

        # Make sure that we can go to ourselves by the empty letter

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

            next.append(state)

        return next

    def __E(self, state, letter='^', 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, letter):

            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, letter, 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 __is_final_state(self, state):

        """Check if a state is a final state."""

        if state in self.final_states:

            return True

        return False

    def __is_list_final(self, states):

        """Check if at least one state in the list "states" is final"""

        for s in states:

            if self.__is_final_state(s):

                return True

        return False

    def __get_temp_record(self, num_letters):

        """Create a record (for the DFA table) that has the proper number

        of slots"""

        blank = None

        return [blank for i in range(num_letters + 3)]

    def __get_possible_letters(self):

        """Create a list of all the possible letters for the NFA,

        and store it in possible_letters"""

        # Get the list of all letters

        possible_letters = []

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

            if letter not in possible_letters and letter != '^':

                possible_letters.append(letter)

        possible_letters = self.__unique_sort(possible_letters)

        self.possible_letters = possible_letters

    def __generate_dfa_table(self):

        """Generate a table for the DFA representation of the NFA entered earlier"""

        # Get all the possible letters

        self.__get_possible_letters()

        # Prime the dfa table with the first state

        self.make_basic_record(self.__E(0))

        # Loop until we resolve every letter in the table

        while self.find_unresolved_letter() != (-1, -1):

            (record, letter_pos) = self.find_unresolved_letter()

            self.resolve_letter(record, letter_pos)

    def resolve_letter(self, record, letter_pos):

        """Resolve a letter in the table, either adding a new entry if the

        required state doesn't already exist, or putting a link to

        an existing state"""

        # Get the NFA equivalent multi-state

        fromstates = self.dfa_table[record][2]

        tostates = []

        # Find all the states we can go to from our multi-state.

        # It is _EXTREMELY_ important that you call E(s) for every state that

        # you can get to, otherwise you miss certain situations.

        for from_s in fromstates:

            for next_s in self.__next_states(from_s, self.possible_letters[letter_pos-3]):

                tostates.extend(self.__E(next_s))

        tostates = self.__unique_sort(tostates)

        # Make the letter we are trying to resolve point to a record in the table.

        # make_basic_record() will return the correct record, even if it needs to

        # create a new one.

        self.dfa_table[record][letter_pos] = self.make_basic_record(tostates)

    def find_unresolved_letter(self):

        """Returns an index pair of an unresolved letter that exists in the dfa_table.

        If there are no more letters, return (-1, -1)"""

        for i in range(len(self.dfa_table)):

            for j in range(len(self.possible_letters)):

                if self.dfa_table[i][j+3] == None:

                    return (i, j+3)

        return (-1, -1)

    def make_basic_record(self, from_states):

        """Create a record, if necessary, for the states "from_states."

        If a corresponding state already exists, return it's index. A new state

        will have everything but the letters filled in."""

        if self.dfa_state_exists(from_states) == -1: #doesn't exist

            temp_record = self.__get_temp_record(len(self.possible_letters))

            recordnum = len(self.dfa_table)

            temp_record[1] = recordnum

            temp_record[2] = self.__unique_sort(from_states)

            temp_record[0] = self.__is_list_final(from_states)

            self.dfa_table.append(temp_record)

        # always return a re-call of the function. This will not fail, since a new

        # record is added above if a record does not already exist.

        return self.dfa_state_exists(from_states)

    def dfa_state_exists(self, from_states):

        """Find out if this state already exists in the dfa table.

        If it does exist, return it's dfa state name.

        If it does not exist, return -1"""

        sorted_states = self.__unique_sort(from_states)

        for i in range(len(self.dfa_table)):

            if self.dfa_table[i][2] == sorted_states:

                return self.dfa_table[i][1]

        return -1

if __name__ == '__main__':

    automaton = nfa()

    automaton.main_menu()