from collections import defaultdict

'''
   Aufgabe 2 + 3: Infrastruktur, Determinisierung
'''

class NFA:
    def __init__(self, initial, trns, final):
        self.initial = initial
        self.final = set(final)
        self.trns = defaultdict(lambda:defaultdict(set))
        for (src, char, tgt) in trns:
            self.trns[src][char].add(tgt)

    def closure(self, state):
        reachable = set([state])
        agenda = [state]
        while agenda:
            state = agenda.pop()
            for other in self.trns.get(state, dict()).get('', []):
                reachable.add(other)
                agenda.append(other)
        return reachable
    

    def recognize(self, strng):
        stack = [(self.initial, strng)]
        while stack:
            #print(stack)  #nuetzlich zum Debuggen, zeigt Zustaende und verbleibenden String
            (state, strng) = stack.pop()
            if strng == '':
                if state in self.final:
                    return True
            else:
                for epsi in self.closure(state):
                    for other in self.trns.get(epsi, {}).get(strng[0], []):
                        stack.append((other, strng[1:]))
        return False


    def removeEpsilon(self):
        new = defaultdict(lambda: defaultdict(set))
        for src in self.trns:
            for epsi in self.closure(src):
                if epsi in self.final:
                   self.final.add(src)
                for (char, tgts) in self.trns.get(epsi, {}).items():
                    if char:   
                        closure_tgts = set()
                        for tgt in tgts:
                            closure_tgts |= self.closure(tgt)
                        new[src][char] = closure_tgts | self.trns[src][char]
        self.trns = new 


    def states(self):
        nodes = set()
        for src in self.trns:
            nodes.add(src)
            for char in self.trns[src]:
                for tgt in self.trns[src][char]:
                    nodes.add(tgt)
        return nodes

    def has_transition(self, src, char, tgt):
        try:
            return tgt in self.trns[src][char]

        except KeyError:
            return False

    def generate(self):
       stack = [(self.initial, '')]
       while stack:
           (state, strng) = stack.pop(0)
           if state in self.final:
               yield strng
           for (char, tgts) in self.trns.get(state, {}).items():
               for tgt in tgts:
                   stack.append((tgt, strng + char))

    def transitions(self):
        return [] # Ersetze dies mit richtigen Code! 

    def is_deterministic(self):
        return False # Falsch ist nicht immer richtig... ersetze das mit richtigen code

    def determinize(self):
        # Code hier!
        return NFA(0, [], []) # Ersetze dies mit richtigen Code!