Returns a NFA that reads the intersection of the NFAs in
    input.

    Let :math:`A_1 = (Σ,S_1,S_1^0,ρ_1,F_1)` and :math:`A_2 =(Σ,
    S_2,S_2^0,ρ_2,F_2)` be two NFAs.
    There is a NFA :math:`A_∧` that runs simultaneously both
    :math:`A_1` and :math:`A_2` on the input word,
    so :math:`L(A_∧) = L(A_1)∩L(A_2)`.
    It is defined as:

    :math:`A_∧ = ( Σ , S , S_0 , ρ , F )`

    where

    • :math:`S = S_1 × S_2`
    • :math:`S_0 = S_1^0 × S_2^0`
    • :math:`F = F_1 × F_2`
    • :math:`((s,t), a, (s_X , t_X)) ∈ ρ` iff :math:`(s, a,s_X )
      ∈ ρ_1` and :math:`(t, a, t_X ) ∈ ρ_2`

    :param dict nfa_1: first input NFA;
    :param dict nfa_2: second input NFA;
    :return: *(dict)* representing the intersected NFA.

def nfa_intersection(nfa_1: dict, nfa_2: dict) -> dict:
    """ Returns a NFA that reads the intersection of the NFAs in
    input.

    Let :math:`A_1 = (Σ,S_1,S_1^0,ρ_1,F_1)` and :math:`A_2 =(Σ,
    S_2,S_2^0,ρ_2,F_2)` be two NFAs.
    There is a NFA :math:`A_∧` that runs simultaneously both
    :math:`A_1` and :math:`A_2` on the input word,
    so :math:`L(A_∧) = L(A_1)∩L(A_2)`.
    It is defined as:

    :math:`A_∧ = ( Σ , S , S_0 , ρ , F )`

    where

    • :math:`S = S_1 × S_2`
    • :math:`S_0 = S_1^0 × S_2^0`
    • :math:`F = F_1 × F_2`
    • :math:`((s,t), a, (s_X , t_X)) ∈ ρ` iff :math:`(s, a,s_X )
      ∈ ρ_1` and :math:`(t, a, t_X ) ∈ ρ_2`

    :param dict nfa_1: first input NFA;
    :param dict nfa_2: second input NFA;
    :return: *(dict)* representing the intersected NFA.
    """
    intersection = {
        'alphabet': nfa_1['alphabet'].intersection(nfa_2['alphabet']),
        'states': set(),
        'initial_states': set(),
        'accepting_states': set(),
        'transitions': dict()
    }
    for init_1 in nfa_1['initial_states']:
        for init_2 in nfa_2['initial_states']:
            intersection['initial_states'].add((init_1, init_2))

    intersection['states'].update(intersection['initial_states'])

    boundary = set()
    boundary.update(intersection['initial_states'])
    while boundary:
        (state_nfa_1, state_nfa_2) = boundary.pop()
        if state_nfa_1 in nfa_1['accepting_states'] \
                and state_nfa_2 in nfa_2['accepting_states']:
            intersection['accepting_states'].add((state_nfa_1, state_nfa_2))
        for a in intersection['alphabet']:
            if (state_nfa_1, a) not in nfa_1['transitions'] \
                    or (state_nfa_2, a) not in nfa_2['transitions']:
                continue
            s1 = nfa_1['transitions'][state_nfa_1, a]
            s2 = nfa_2['transitions'][state_nfa_2, a]

            for destination_1 in s1:
                for destination_2 in s2:
                    next_state = (destination_1, destination_2)
                    if next_state not in intersection['states']:
                        intersection['states'].add(next_state)
                        boundary.add(next_state)
                    intersection['transitions'].setdefault(
                        ((state_nfa_1, state_nfa_2), a), set()).add(next_state)
                    if destination_1 in nfa_1['accepting_states'] \
                            and destination_2 in nfa_2['accepting_states']:
                        intersection['accepting_states'].add(next_state)

    return intersection