from collections import defaultdict

'''
   Aufgabe 1: Schnitt von deterministischen Automaten.
'''

class DFA:
    def __init__(self, initial, transitions, final):
        self.initial = initial
        self.final = set(final)
        self.trns = defaultdict(dict)
        for (src, char, tgt) in transitions:
            self.trns[src][char] = tgt
    
    def recognize(self, strng):
         state = self.initial
         try:
             for char in strng:
                 state = self.trns[state][char]
         except KeyError: # impliziter Nicht-Endzustand
             return False
         return state in self.final

    def states(self):
        nodes = set()
        for src in self.trns:
            nodes.add(src)
            for char in self.trns[src]:
                nodes.add(self.trns[src][char])
        return nodes
     
    def transitions(self):
        ret = []
        for src in self.trns:
            for char in self.trns[src]:
                ret.append((src, char, self.trns[src][char])) 
        return ret

    
    def intersect(self, other):
         # Dein Code hier
         return DFA(0, [], []) # Ersetze dies mit richtigen code!