4
$\begingroup$

In general, the size of the DFA resulting from the union of two DFAs A and B is O(|A|.|B|) in the worst case (usually the product construction is used to compute the union).

Let's consider the class of 'synchronized DFAs' as the class of DFAs having a synchronizing word : https://en.wikipedia.org/wiki/Synchronizing_word

After looking at some examples of synchronized DFAs A and B, it seems possible to always build a synchronized DFA for the UNION of A and B with a size O(|A| + |B|) in the worst case.

Does anybody have any information, proof or paper about the union of two synchronized DFAs in O(|A| + |B|) ?

Many thanks, Luz

$\endgroup$
5
$\begingroup$

Your conjecture is wrong. Consider the following languages:

  • $L_1$ is the language of words over $\{a,b,c\}$ such that the number of $b$s after the last $a$ is a multiple of $x$.

  • $L_2$ is the language of words over $\{a,b,c\}$ such that the number of $c$s after the last $a$ is a multiple of $y$.

The minimal DFA of $L_1$ contains $x$ states, and that of $L_2$ contains $y$ states. Both DFAs have $a$ as a synchronizing word. The minimal DFA for $L_1\cup L_2$ contains $xy$ states (and also has $a$ as a synchronizing word).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.