print("++++ abab|baba ++++")

delta = {("eps",'a'): ["eps","1a"], ("eps",'b'): ["eps","2b"],
         ("1a",'a'): [],            ("1a",'b'): ["1ab"],
         ("1ab",'a'): ["1aba"],     ("1ab",'b'): [],
         ("1aba",'a'): [],          ("1aba",'b'): ["1abab"],
         ("1abab",'a'): ["1abab"],  ("1abab",'b'): ["1abab"],
         
         ("2b",'a'): ["2ba"],       ("2b",'b'): [],
         ("2ba",'a'): [],           ("2ba",'b'): ["2bab"],
         ("2bab",'a'): ["2baba"],   ("2bab",'b'): [],
         ("2baba",'a'): ["2baba"],  ("2baba",'b'): ["2baba"],
         }
q0 = "eps" # Startzustand
F = ["1abab","2baba"] # akzeptierende Zustände

def teste(w):
    A = set([q0])
    print(f"Mögliche Zustände zu Beginn: {A}")
    for i,c in enumerate(w):
        A_neu = set(q2 for q in A for q2 in delta[q,c])
        A = A_neu
        print(f"Mögliche Zustände nach dem {i+1}-ten symbol {c}: {A}")
    return any(q in A for q in F)

print(teste("aabbaaba"))
print(teste("abaabbaaba"))

#exit()
############################################################

print("anderer Automat")
        

delta = {('a','0'): ['a','b'],  ('a','1'): ['b'],
         ('b','0'): [],         ('b','1'): ['a'],
        }
q0 = 'a' # Startzustand
F = ['b'] # akzeptierende Zustände


print(teste("1101"))

print(teste("1001"))

print(teste("11"))

print(teste("111"))