Rangkaian DFA yang efisien?

Ada bukti teoretis bahwa konstruksi produk-kartesian naif untuk persimpangan DFA adalah "yang terbaik yang bisa kita lakukan". Bagaimana dengan gabungan dua DFA? Konstruksi sepele melibatkan konversi setiap DFA menjadi NFA, menambahkan transisi epsilon dan menentukan NFA yang dihasilkan. Bisakah kita berbuat lebih baik? Apakah ada batasan yang diketahui pada ukuran DFA penggabungan minimal (dalam hal ukuran "awalan" dan "akhiran" DFA)?

Ya - diketahui bahwa terdapat DFA masing-masing negara dan , sehingga DFA minimal untuk gabungan bahasa yang bersesuaian memiliki status , yang cocok dengan huruf atas yang diketahui. terikat.$m$$n$$m*2^n - 2^{n-1}$

Ini pertama kali diamati oleh Maslov pada tahun 1970, dan ditemukan kembali oleh Yu, Zhuang, dan K. Salomaa dalam makalah mereka, "Kompleksitas negara dari beberapa operasi dasar pada bahasa reguler", TCS 125 (1994), 315-328.