I have two finite sets of strings S_1, S_2 that are described by DFAs (e.g. these sets are regular languages, but I want to emphasize the fact that they are finite of known maximum length).

I need to write an algorithm (running in software) that tells you whether these two sets are disjoint. My strategy is as follows:

• Implement two (halting) automata M_1 and M_2 that accept S_1, S_2 respectively. M_1 has b_1 states and M_2 has b_2 states.
• Implement their product automata M_1 × M_2 (it has b_1 × b_2 states.
• Use a BFS algorithm to determine whether M_1 × M_2 is empty or not.

I expect this to work nicely on software, modulo the quadratic scaling on the amount of states. I wanted to know: Is this really better than enumerating S_1, S_2 without DFAs and computing the intersection? At first glance it looks like it, but on second thought isn't that exactly that what the BFS algorithm will end up doing?

In case it is necessary:

• S_1 is the set of strings of length between a_1 and b_1 over an alphabet E_1, followed by strings of length between a_2 and b_2 over another alphabet E_2 (with E_1 intersection E_2 = emptyset and so on k times.
• S_2 is a similar set with same alphabets but with different a_i', b_i' and different k'.
• Therefore, my automata look like: count between a_1 and b_1 symbols of E_1 then count between a_2 and b_2 symbols of E_2 and so forth.

(I know that given these sets, an answer can be given by just looking at the alphabets and the intervals [a_i, b_i], [a_i', b_i'] and k, k' etc but there are additional constraints that make combinatorial approaches really difficult and I don't want to enter there just yet.)