[phython] e-NFA를 DFA로 만드는 프로그램

import collections

class Delta():
    def __init__(self):
        self.NFA_state = collections.defaultdict(list)

        self.DFA_state = collections.defaultdict(list)
        self.FINAL_state = []
        self.ARC_state = []
        self.START_state = []

    def add_delta(self, current_state, arc, next_state):
        self.NFA_state[current_state].append([str(arc), list(map(str, next_state))])

    def add_final(self, number):
        self.FINAL_state = number

    def add_arc(self, number):
        self.ARC_state = number

    def add_start(self, number):
        self.START_state = str(number)

    def NFA_show(self):
        print('e-NFA!')
        for i in self.NFA_state:
            self.temp_state = self.NFA_state[i]
            for j in range(len(self.temp_state)):
                print(" delta(", str(i), ',' + self.temp_state[j][0], ") = ", "{", ",".join(self.temp_state[j][1]), "}", sep='')


    def DFA_show(self):
        print('DFA!')
        for key, values in self.DFA_state.items():
            values = list(set(values))
            for value in values:
                print(" delta (" , "{" , ",".join(key) , "}", "," , value[0],  ") = ", "{" , ",".join(value[1:]), "}", sep='')

    def convert(self):
        closure_start = self.closure([self.START_state])
        self.stack = [[self.START_state]+closure_start] # 시작 state만 미리 집어넣기
        while len(self.stack):

            self.number_list = tuple(self.stack[0])
            del self.stack[0] # 사용한 stack 값 제거
            self.ret = [ [] for i in range(len(self.ARC_state))] # 각 아크에 해당하는 state 만들기
            for i in self.number_list: # 찾으려는 start가 여러개 일 때 하나씩 확인
                for index, arc in enumerate(self.ARC_state): # arc의 개수만큼 확인하기
                    for List in self.NFA_state[i]:
                        arc_check = List[0]
                        if arc_check == arc:
                            self.ret[index].extend(List[1])
                            closure_temp = self.closure(List[1])
                            self.ret[index].extend(closure_temp)
                        elif arc_check == 'e':
                            self.ret[index].extend(List[1])
                            closure_temp = self.closure(List[1])
                            self.ret[index].extend(closure_temp)
        
            for i, temp_list in enumerate(self.ret): # 중복 제거
                sorted_temp_list = list(map(str, sorted(list(map(int, set(temp_list))))))
                self.ret[i] = sorted_temp_list

            for index, arc in enumerate(self.ARC_state): # arc의 개수만큼 생성된 ret을 일단 DFA_state에 넣기
                temp = collections.deque()
                temp.append(arc)
                for y in self.ret[index]:
                    temp.append(y)
                
                if len(list(temp)) == 1:
                    continue

                self.DFA_state[self.number_list].append(tuple(temp))
                
                temp.popleft()
                if tuple(temp) in self.DFA_state:
                    pass
                else:
                    self.stack.append(tuple(temp))
    
    def closure(self, number):
        cloure_list = []
        for i in range(len(number)):
            List = self.NFA_state[number[i]]
            for j in range(len(List)):
                if List[j][0] == 'e':
                    for k in range(len(List[j][1])):
                        temp = List[j][1][k] 
                        cloure_list.append(temp) 
                        cloure_list.extend(self.closure(temp))
        return cloure_list
    
    def search(self, strings):
        string_list = [self.START_state]
        string_list_next = []
        for string in strings:
            for temp in string_list:           
                for current_state, exp in self.DFA_state.items():
                    if temp in current_state:
                        for exp_list in exp:
                            if string == exp_list[0]:
                                string_list_next.extend(exp_list[1:])
                                string_list_next = sorted(list(set(string_list_next)))
                                string_list = string_list_next
                                string_list_next = []


        string_list = list(map(str, sorted(list(map(int, set(string_list))))))
        for check in string_list:
            if check in self.FINAL_state:
                print("Accpted")
                return 
        else: 
            print("Rejected")
            return 

if __name__ == "__main__":
    delta = Delta()
    # 모든 state name는 str형식으로 자동변환됨
    delta.add_start(('0'))
    delta.add_arc(('a', 'b'))
    delta.add_final(['10'])
    delta.add_delta('0', 'e', ['1','7'])
    delta.add_delta('1', 'e', ['2','4'])
    delta.add_delta('2', 'a', ['3'])
    delta.add_delta('3', 'e', ['6'])
    delta.add_delta('4', 'b', ['5'])
    delta.add_delta('5', 'e', ['6']) 
    delta.add_delta('6', 'e', ['1','7'])
    delta.add_delta('7', 'a', ['8'])
    delta.add_delta('8', 'b', ['9'])
    delta.add_delta('9', 'b', ['10'])

    delta.NFA_show()
    delta.convert()
    delta.DFA_show()

    delta.search("abb")