Effiziente Verkettung von DFAs?

Es gibt theoretische Beweise dafür, dass die naive kartesische Produktkonstruktion für die Schnittmenge von DFAs "das Beste ist, was wir tun können". Was ist mit der Verkettung von zwei DFAs? Die triviale Konstruktion besteht darin, jeden DFA in einen NFA umzuwandeln, einen Epsilon-Übergang hinzuzufügen und den resultierenden NFA zu bestimmen. Können wir es besser machen? Gibt es eine bekannte Grenze für die Größe des minimalen Verkettungs-DFA (in Bezug auf die Größen der DFAs "Präfix" und "Suffix")?

Ja - es ist bekannt, dass es DFAs mit bzw. n Zuständen gibt, so dass der minimale DFA für die Verkettung der entsprechenden Sprachen m ∗ 2 n - 2 n - 1 Zustände hat, was mit der bekannten Obergrenze übereinstimmt.$m$$n$$m*2^n - 2^{n-1}$

Dies wurde erstmals 1970 von Maslov beobachtet und von Yu, Zhuang und K. Salomaa in ihrem Aufsatz "Die Zustandskomplexität einiger grundlegender Operationen mit regulären Sprachen", TCS 125 (1994), 315-328, wiederentdeckt.