NFA -> DFA

from collections import deque

from math import factorial as f

def nCr(n, r):
    if n < r:
        return 0
    return f(n) / (f(r) * f(n-r))

def generate_all_permutations(elements):
    n = len(elements)

    perms = elements[: ]

    low = 0
    size = nCr(n, 1)
    ctr = 0

    while len(perms) < 2 ** n - 1:

        for element1 in perms[low: low + size]:
            for element2 in xrange(n):
                if ctr == 0: #there's no tuple first up
                    x = element1
                else:
                    x = element1[-1] #the last element of the tuple would be compared

                if element2 > x:
                    if ctr == 0:
                        element_n = [element1, element2]
                    else:
                        element_n = list(element1)
                        element_n.append(element2)

                    perms.append(tuple(element_n))

        ctr += 1
        low = low + size
        size = nCr(n, ctr)

    return perms

def format(lst, n):

    new_str = ""

    labels = list()

    for i in xrange(n):
        labels.append(str(i))

    for number in lst[n: ]:
        labels.append("".join(map(str, number)))


    return labels

def get_all_labels(lst):
    '''
    makes the powerset out of the list
    '''
    return format(generate_all_permutations(lst), len(lst))


transition_table_DFA = '''3 2
0 1 2
0 1
0
2
0
1
2
1
0
1'''


#the first line would contain the no of states and the letters in the alphabet
#the second line would contain the labels of the states
#the third line would contain the letters in the alphabet accepted by the automaton
#the fourth line would contain the starting state
#the fifth line would contain the accepting states separated by spaces
#and onwards would describe the table

#this one is for strings ending in 10
transition_table_NFA = '''4 2
0 1 2 d
0 1
0
2
0
0 1
2
d
d
d
d
d'''

#this one is for strings having 11 as a substring
transition_table_NFA2 = '''4 2
0 1 2 d
0 1
0
2
0
0 1
d
2
2
2
d
d'''

#this is for strings that end with 'abc' over the alphabet a, b, c
transition_table_NFA3 = '''5 3
0 1 2 3 d
a b c
0
3
0 1
0
0
d
2
d
d
d
3
d
d
d
d
d
d'''

#this one is for strings having 101 as a substring
transition_table_NFA4 = '''5 2
0 1 2 3 d
0 1
0
3
0
0 1
2
d
d
3
3
3
d
d'''




class State(object):
    '''
    ADT for handling each state in the automaton
    '''

    def __init__(self, label):
        '''
        initializer for a state object
        '''
        self._label = label #the label of the state

        #dictionaries that'll have decision values as the key and the other states as the values
        self._transitions = dict()
        self._is_accepting = False
        self._is_starting = False

    def __repr__(self):
        '''
        representation of the state object
        '''
        return str(self._label)

    def __str__(self):
        '''
        string representation of the state object
        '''
        st = "\nState " + str(self._label) + "\n"
        st += "Transitions: " + str(self._transitions) + "\n"

        return st

    def add_neighbor(self, symbol, other_state):
        '''
        adds the neighbor to the state. state (symbol) other_state
        '''
        if symbol in self._transitions:
            self._transitions[symbol].add(other_state)

        else:
            self._transitions[symbol] = set([other_state])

        #print self._transitions

    def get_label(self):
        '''
        returns the label of a state
        '''
        return self._label

    def get_neighbor(self, symbol):
        '''
        returns the neighbor of the state with symbol
        '''
        neighbor_list = list()
        # print "symbol", symbol, "transitions ", self._transitions

        for state in self._transitions[symbol]:
            neighbor_list.append(state)

        return neighbor_list

    def get_transitions(self):
        return self._transitions

    def set_accepting(self):
        self._is_accepting = True

    def set_starting(self):
        self._is_starting = True


class Automaton(object):
    '''
    Automaton ADT. Feed a transition table.
    '''

    def __init__(self, transition_table, state_list = list()):
        '''
        initializer for the Automaton object
        '''
        self._states = state_list

        self._accepting_states = set()
        self._starting_state = None
        self._transition_table = transition_table
        self._label_set = set() #this will have all the labels of the states in the automaton

        for state in self._states:
            self._label_set.add(state)


        if self._transition_table == '':
            return

        #pair of lines constitute the transitions for each state
        #first line gives the state labels for symbol 0
        #second line gives the state labels for symbol 1

        lines = transition_table.split("\n")

        #0th line has the no of states and no of symbols
        self._no_of_states, self._no_of_symbols = map(int, lines[0].split())

        #1st line has the state labels
        #state_labels = lines[1].split()
        #print state_labels

        #allocating the states
        num_states = len(state_list)
        if num_states == 0:
            for label in lines[1].split():
                self._states.append((State(label)))
                self._label_set.add(label)


        #2nd line has the symbols
        self._symbols = lines[2].split()
        #print symbols

        #print self._accepting_states
        state_ctr = 0

        if num_states == 0:
            for i, line in enumerate(lines[5: ]):

                neighbor_labels = line.split()

                symbol = self._symbols[i % self._no_of_symbols]

                #for the first of the pair of lines, it gives
                for label in neighbor_labels:
                    dest = self.get_state(label)
                    self._states[i / self._no_of_symbols].add_neighbor(symbol, dest)
                    #print dest

        # #setting the neighbors of the dead state
        # for symbol in self._symbols:
        #   #a dead state should stay dead regardless of the symbol it receives
        #   self._states[-1].add_neighbor(symbol, self._states[-1])

        # self._states.pop() #temporary fix

        #3rd line has the starting state
        self._starting_state = self.get_state(lines[3])

        #print self._starting_state

        #4th line has the accepting states
        self._accepting_states = set()
        for label in lines[4].split():
            self._accepting_states.add(self.get_state(label))

        #print self._accepting_states

    def __str__(self):
        '''
        string representation of the object
        '''
        st = "Member states: "

        for state in self._states:
            st += str(state)

        return st

    def update_transitions(self, table):

        lines = table.split("\n")
        #print lines

        self._no_of_states, self._no_of_symbols = map(int, lines[0].split())
        self._symbols = lines[2].split()

        self._starting_state = self.get_state(lines[3])

        for label in lines[4].split():
            self._accepting_states.add(self.get_state(label))

        #this populates the unary states

        for i, line in enumerate(lines[5: len(lines) - self._no_of_symbols]):

            source_label = self._states[i / self._no_of_symbols].get_label()

            symbol = self._symbols[i % self._no_of_symbols]

            dest_label = ''

            for dest in line.split():
                dest_label += dest
                #print "d: ", dest_label

            dest_state = self.get_state(dest_label)

            self._states[i / self._no_of_symbols].add_neighbor(symbol, dest_state)
            #print i / self._no_of_symbols

        for symbol in self._symbols:
            self._states[-1].add_neighbor(symbol, self._states[-1])

        #now for the hybrid states
        dest_label_list = list()

        for state in self._states[3: -1]:

            for symbol in self._symbols:
                complex_state_label = state.get_label()
                dest_label = ""

                for st_label in complex_state_label:

                    dest = self.get_state(st_label)
                    lab = dest.get_neighbor(symbol)[0].get_label()

                    if lab not in dest_label and lab != 'd':
                        dest_label += lab

                if len(dest_label) == 0:
                    dest_label = 'd'

                state.add_neighbor(symbol, self.get_state(dest_label))

    def delta(self, inp_str):
        '''
        given an input string, it would return the end state which would be reached once the string is processed
        '''
        route = ""
        visited_labels = list()

        end_state = self.get_state(self._starting_state.get_label())

        for symbol in inp_str:
            visited_labels.append(end_state.get_label())
            #print end_state.get_transitions()[symbol]
            end_state, = end_state.get_transitions()[symbol]
            #print end_state.get_label()
            end_state = self.get_state(end_state.get_label())

        route = ' -> '.join(visited_labels)

        new_state = set()

        #updating the accepting states
        for ac_st in self._accepting_states:
            for state in self._states:
                if ac_st.get_label() in state.get_label():
                    new_state.add(state)

        self._accepting_states = new_state

        #print new_state

        if end_state in self._accepting_states:
            print "%s is accepted" % (inp_str)

        else: #stopping at die status
            print "%s is rejected" % (inp_str)

        return route

    def minimize(self):
        '''
        removes the 'redundant' states from the transition table
        '''
        #starting_state = self.get_state(self._starting_state.get_label())
        state = self._starting_state

        queue = deque()
        queue.append(state)
        visited = set()
        i = 0

        #while len(queue) != 0:
        for _ in xrange(5):
            if len(queue) == 0:
                break
            state = queue.popleft()
            visited.add(state.get_label())

            neighbors = self.get_all_neighbors(state.get_label())

            #print "n", neighbors

            for neighbor in neighbors:
                if neighbor.get_label() not in visited:
                    queue.append(neighbor)
                    visited.add(neighbor.get_label())

        updated_states = list()

        for label in visited:
            updated_states.append(self.get_state(label))

        self._states = updated_states
        self._states.sort() #this is optional

    #getters
    def get_accepting_states(self):
        '''
        returns the set of accepting_states of the automaton
        '''
        return self._accepting_states

    def get_states(self):
        '''
        returns the list of states of the automaton
        '''
        return self._states

    def get_starting_state(self):
        '''
        returns the starting state of the automaton
        '''
        return self._starting_state

    def get_state(self, label):
        '''
        returns the state in the automaton with the label 'label'
        '''

        for state in self._states:
            if state._label == label:
                return state

    def get_no_of_states(self):
        '''
        returns th no of states in the automaton
        '''
        return (self._no_of_states)

    def get_all_neighbors(self, label):
        '''
        returns the list of neighbors of the state with label 'label'
        '''
        state = self.get_state(label)

        neighbors = list()

        for symbol in self._symbols:
            neighbors.append(State(state.get_neighbor(symbol)[0].get_label()))

        #print neighbors
        return neighbors

    #setters
    def set_accepting_states(self, accepting_states):
        '''
        sets the accepting states of the automaton
        '''
        self._accepting_states = accepting_states

    def set_starting_state(self, starting_state):
        '''
        sets the starting state of the automaton
        '''
        self._starting_state = starting_state


def gen_states(n):
    '''
    returns a list of states whose labels are the power_set of n
    works!
    '''
    labels = get_all_labels(range(n))
    labels.append('d')

    #print labels

    state_list = [State(label) for label in labels]

    return state_list

def test():

    table = transition_table_NFA4

    NFA = Automaton(table)

    DFA = Automaton('', gen_states(NFA.get_no_of_states() - 1))

    DFA.update_transitions(table)

    #print DFA
    DFA.minimize()

    print(DFA)
    print DFA.delta('101')

def main():
    test()

if __name__ == '__main__':
    main()