def dfa_union(dfa_1: dict, dfa_2: dict) -> dict:
    """ Returns a DFA accepting the union of the input DFAs.

    Let :math:`A_1 = (Σ, S_1 , s_{01} , ρ_1 , F_1 )` and
    :math:`A_2 = (Σ, S_2 , s_{02} , ρ_2 , F_2 )` be two completed
    DFAs.
    Then there is a DFA :math:`A_∨` that runs simultaneously both
    :math:`A_1` and :math:`A_2` on the input word
    and accepts when one of them accepts.
    It is defined as:

    :math:`A_∨ = (Σ, S_1 × S_2 , (s_{01} , s_{02} ), ρ, (F_1 ×
    S_2 ) ∪ (S_1 × F_2 ))`

    where

    :math:`ρ((s_1 , s_2 ), a) = (s_{X1} , s_{X2} )` iff
    :math:`s_{X1} = ρ_1 (s_1 , a)` and :math:`s_{X2} = ρ(s_2 , a)`

    Proposed implementation guarantees resulting DFA has only **reachable**
    states.

    :param dict dfa_1: first input DFA;
    :param dict dfa_2: second input DFA.
    :return: *(dict)* representing the united DFA.
    """
    dfa_1 = deepcopy(dfa_1)
    dfa_2 = deepcopy(dfa_2)
    dfa_1['alphabet'] = dfa_2['alphabet'] = dfa_1['alphabet'].union(
        dfa_2['alphabet'])  # to complete the DFAs over all possible transition
    dfa_1 = dfa_completion(dfa_1)
    dfa_2 = dfa_completion(dfa_2)

    union = {
        'alphabet': dfa_1['alphabet'].copy(),
        'states': {(dfa_1['initial_state'], dfa_2['initial_state'])},
        'initial_state': (dfa_1['initial_state'], dfa_2['initial_state']),
        'accepting_states': set(),
        'transitions': dict()
    }

    boundary = set()
    boundary.add(union['initial_state'])
    while boundary:
        (state_dfa_1, state_dfa_2) = boundary.pop()
        if state_dfa_1 in dfa_1['accepting_states'] \
                or state_dfa_2 in dfa_2['accepting_states']:
            union['accepting_states'].add((state_dfa_1, state_dfa_2))
        for a in union['alphabet']:
            # as DFAs are completed they surely have the transition
            next_state_1 = dfa_1['transitions'][state_dfa_1, a]
            next_state_2 = dfa_2['transitions'][state_dfa_2, a]
            if (next_state_1, next_state_2) not in union['states']:
                union['states'].add((next_state_1, next_state_2))
                boundary.add((next_state_1, next_state_2))
            union['transitions'][(state_dfa_1, state_dfa_2), a] = \
                (next_state_1, next_state_2)

    return union
def dfa_union ( dfa_1 : dict , dfa_2 : dict ) -> dict : dfa_1 = deepcopy ( dfa_1 ) dfa_2 = deepcopy ( dfa_2 ) dfa_1 [ 'alphabet' ] = dfa_2 [ 'alphabet' ] = dfa_1 [ 'alphabet' ] . union ( dfa_2 [ 'alphabet' ] ) dfa_1 = dfa_completion ( dfa_1 ) dfa_2 = dfa_completion ( dfa_2 ) union = { 'alphabet' : dfa_1 [ 'alphabet' ] . copy ( ) , 'states' : { ( dfa_1 [ 'initial_state' ] , dfa_2 [ 'initial_state' ] ) } , 'initial_state' : ( dfa_1 [ 'initial_state' ] , dfa_2 [ 'initial_state' ] ) , 'accepting_states' : set ( ) , 'transitions' : dict ( ) } boundary = set ( ) boundary . add ( union [ 'initial_state' ] ) while boundary : ( state_dfa_1 , state_dfa_2 ) = boundary . pop ( ) if state_dfa_1 in dfa_1 [ 'accepting_states' ] or state_dfa_2 in dfa_2 [ 'accepting_states' ] : union [ 'accepting_states' ] . add ( ( state_dfa_1 , state_dfa_2 ) ) for a in union [ 'alphabet' ] : next_state_1 = dfa_1 [ 'transitions' ] [ state_dfa_1 , a ] next_state_2 = dfa_2 [ 'transitions' ] [ state_dfa_2 , a ] if ( next_state_1 , next_state_2 ) not in union [ 'states' ] : union [ 'states' ] . add ( ( next_state_1 , next_state_2 ) ) boundary . add ( ( next_state_1 , next_state_2 ) ) union [ 'transitions' ] [ ( state_dfa_1 , state_dfa_2 ) , a ] = ( next_state_1 , next_state_2 ) return union
Returns a DFA accepting the union of the input DFAs.

    Let :math:`A_1 = (Σ, S_1 , s_{01} , ρ_1 , F_1 )` and
    :math:`A_2 = (Σ, S_2 , s_{02} , ρ_2 , F_2 )` be two completed
    DFAs.
    Then there is a DFA :math:`A_∨` that runs simultaneously both
    :math:`A_1` and :math:`A_2` on the input word
    and accepts when one of them accepts.
    It is defined as:

    :math:`A_∨ = (Σ, S_1 × S_2 , (s_{01} , s_{02} ), ρ, (F_1 ×
    S_2 ) ∪ (S_1 × F_2 ))`

    where

    :math:`ρ((s_1 , s_2 ), a) = (s_{X1} , s_{X2} )` iff
    :math:`s_{X1} = ρ_1 (s_1 , a)` and :math:`s_{X2} = ρ(s_2 , a)`

    Proposed implementation guarantees resulting DFA has only **reachable**
    states.

    :param dict dfa_1: first input DFA;
    :param dict dfa_2: second input DFA.
    :return: *(dict)* representing the united DFA.