AFD.py

class State:
    state_id_counter = 0
    
    def __init__(self, initial=False, final=False):
        #setting an unique id
        self.id = State.state_id_counter
        State.state_id_counter += 1
        #setting params
        self.initial = initial
        self.final = final
        self.transition = {}

    def add_transition(self, char, state):
        if char in self.transition:
            self.transition[char].append(state)
        else:
            self.transition[char] = [state]

    def is_deterministic(self):
        return all(map(
            lambda k: len(self.transition[k]) <= 1,
            self.transition.keys()))

    def __acronyme(self):
        s = "State"
        
        if self.final:
            s = "F" + s
            
        if self.initial:
            s = "I" + s

        return s

    def __repr__(self):
        t = {}
        for k in self.transition:
            t[k] = str(self.transition[k][0])
        
        return "<{} {}: {}>".format(self.__acronyme(), self.id, t)

    def __str__(self):
        return "<{} {}>".format(self.__acronyme(), self.id)

class AFD:
    def __init__(self, *states):
        self.states = states
        self.__last_lecture = []
        
        c = 0
        for s in states:
            #check all states are 'deterministic'
            if not s.is_deterministic():
                raise Exception("A non determinist state has been added !! :'(")

            #set initial state and check there is not too much
            if s.initial:
                c += 1
                self.initial_state = s
                if c > 1:
                    raise Exception("To many initial states !! :'(")

    def get_last_lecture_sequence(self):
        return self.__last_lecture
    
    def read(self, *word):
        self.__last_lecture = []
        current = self.initial_state
        for c in word:
            if c in current.transition:
                self.__last_lecture.append(current)
                current = current.transition[c][0]
            else:
                raise Exception("No transition for this char : {} !! :'(".format(c))
        #check if the last state is a valid final state
        if not current.final:
            raise Exception("Not a valid final state !! :'(")

        return True

    def is_word_recognized(self, *word):
        try:
            return self.read(*word)
        except:
            return False

    def complete(self, *alphabet):
        if alphabet == (): #autodetect alphabet from states
            alphabet = []
            for s in self.states:
                alphabet.extend(s.transition.keys())

        #remove duplicate
        alphabet = list(set(alphabet))

        #create the absorbing state
        absorbing_state = State()
        for c in alphabet:
            absorbing_state.add_transition(c, absorbing_state)

        #create all missing transition to the absorbing state
        for s in self.states:
            for c in alphabet:
                if not c in s.transition:
                    s.add_transition(c, absorbing_state)

        #add the absorbing state to the automaton
        self.states = tuple(list(self.states) + [absorbing_state])
        

    def __str__(self):
        s = "<ADF>" + chr(10)
        for state in self.states:
            s += state.__repr__() + chr(10)
        return s[:-1]

    def __repr__(self):
        return str(self)
      
      
if __name__ == "__main__":
    #create states
    s1 = State(initial=True)
    s2 = State(final=True)
    
    #linking them
    s1.add_transition('a', s2)
    s2.add_transition('a', s2)
    s2.add_transition('b', s1)
    
    #create automaton
    automaton = AFD(s1, s2)
    
    #test it
    print ''
    print "WORD\tVALID\tSEQUENCE"
    
    def t(afd, str_word):
        return "{}\t{}".format(
            afd.is_word_recognized(*str_word),
            map(str, afd.get_last_lecture_sequence()))
    
    words = ["a", "aaa", "aaba", "aaab", "abba"]
    for w in words:
        print w, "\t",  t(automaton, w)

    #print the automaton created and the completed one
    print ''
    print automaton
    
    automaton.complete()

    print ''
    print automaton