#!/usr/bin/python3
#

def succ(d, p, a):
    return {q_ for (p_, a_, q_) in d if p_ == p and a_ == a}

def convert(A):
    (Q, S, d, Q0, F) = A

    # New NFA components
    Q_  = set(Q0)
    Q0_ = set(Q0)
    d_  = set()
    F_  = set(F & Q0)

    # Worksets
    d__ = set()
    W   = {(q, a, q_) for (q, a, q_) in d if q in Q0}

    while len(W) > 0:
        q1, a, q2 = W.pop()

        if a != "":
            # complete this branch of code
            # 
        else:
            d__.add( (q1, a, q2) )
            if q2 in F:
                F_.add(q1)

            for b in S | {""}:
                for q3 in succ(d, q2, b):
                    if (q1, b, q3) not in d_ | d__:
                        W.add((q1, b, q3))

    return (Q_, set(S), d_, Q0_, F_)
 
# Example
if __name__ == "__main__":
    Q  = {"q0", "q1", "q2", "q3" }
    S  = {"a", "b"}
    d  = {("q0", "",  "q1"), ("q0", "",  "q2"), ("q0", "a", "q2"),
          ("q1", "",  "q3"), ("q2", "b", "q3"), ("q2", "b", "q2")}
    Q0 = {"q0"}
    F  = {"q3"}

    A  = (Q, S, d, Q0, F)
    
    # Convert A to an equivalent NFA B
    B = convert(A)
    
    (Q_, S_, d_, Q0_, F_) = B
    
    print("Q\'  =", Q_)
    print("S   =",  S_)
    print("d\'  =", d_)
    print("Q0\' =", Q0_)
    print("F\'  =", F_)

# Expected output
#
# Q'  = {'q3', 'q2', 'q0'}
# S   = {'b', 'a'}
# d'  = {('q2', 'b', 'q3'), ('q0', 'b', 'q2'), ('q2', 'b', 'q2'), ('q0', 'a', 'q2'), ('q0', 'b', 'q3')}
# Q0' = {'q0'}
# F'  = {'q3', 'q0'}