from collections import defaultdict

class NFA:
    ''' Die Automaten-Klasse aus der Vorlesung. '''

    def __init__(self, initial, trns, final):
        self.initial = initial
        self.final = set(final)
        self.trns = 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, ''), []):
                reachable.add(other)
                agenda.append(other)
        return reachable

    # 1 - Infrastruktur  
    def states(self):
         #Dein Code
         pass

    def has_transition(self, src, char,tgt):
         #Dein Code
         pass    

    # 2 - recognize ohne Rekursion
    def recognize(self, strng):
         #Dein Code
         pass

    # 3 Epsilon-Kanten eliminieren
    def removeEpsilon(self):
         #Dein Code
         pass


    # 4 Generierung
    def generate(self):
         #Dein Code
         pass