使用乘积DFA判断两个有限字符串集合是否不相交的可行性探讨

我有两个由DFA描述的有限字符串集合S₁、S₂（属于正则语言，且已知最大长度），需要编写软件算法判断二者是否不相交。拟定的策略如下：

• 实现分别接受S₁、S₂的停机自动机M₁（含b₁个状态）和M₂（含b₂个状态）；
• 实现它们的乘积自动机M₁ × M₂（含b₁ × b₂个状态）；
• 用BFS算法判断M₁ × M₂是否为空。

该方法存在状态数二次增长问题，但我不确定它是否比直接枚举S₁、S₂求交集更优，担心BFS本质上和枚举没区别。

补充信息：

• S₁是由E₁字母表上长度在a₁到b₁的字符串，接续E₂字母表上长度在a₂到b₂的字符串（E₁ ∩ E₂ = ∅），以此重复k次组成的集合；
• S₂结构类似，使用相同字母表，但a_i'、b_i'和k'不同；
• 自动机逻辑为：先计数E₁符号数量在a₁到b₁之间，再计数E₂符号数量在a₂到b₂之间，依此类推。

虽可通过字母表、区间[a_i, b_i]、[a_i', b_i']及k、k'等直接判断，但存在额外约束使这种组合判断法难以实现。

内容的提问来源于stack exchange，提问作者zugzwang