Concaténation efficace des DFA?

Il existe des preuves théoriques que la construction de produits cartésiens naïfs pour l'intersection des DFA est "le meilleur que nous pouvons faire". Qu'en est-il de la concaténation de deux DFA? La construction triviale implique la conversion de chaque DFA en NFA, l'ajout d'une transition epsilon et la détermination du NFA résultant. Pouvons-nous faire mieux? Existe-t-il une limite connue sur la taille du DFA à concaténation minimale (en termes de taille des DFA "préfixe" et "suffixe")?

cc.complexity-theory fl.formal-languages automata-theory dfa Aryeh
la source

Réponses:

Oui - il est connu qu'il existe des DFA de et états, respectivement, de sorte que le DFA minimal pour la concaténation des langues correspondantes a états, ce qui correspond à la limite supérieure connue. $m$ $n$ $m*2^n - 2^{n-1}$

Cela a été observé pour la première fois par Maslov en 1970, et redécouvert par Yu, Zhuang et K. Salomaa dans leur article, "La complexité de l'état de certaines opérations de base sur les langues régulières", TCS 125 (1994), 315-328.

Jeffrey Shallit
la source

O (2^{n + m})

$O(2^{n+m})$

m * 2^{n} - 2^{n - 1}

$m*2^n - 2^{n-1}$