Given an $n$-state DFA (over a binary or any fixed alphabet), what is the complexity of computing its Kleene closure DFA? What is the largest possible/known blow-up in the number of states?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ prompted by this question, which, while poorly phrased, contains a valid core I think cstheory.stackexchange.com/questions/34763/… $\endgroup$– AryehMay 16, 2016 at 11:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
You asked a similar question some time ago about concatenation. I gave the references back then and they still apply here. See Yu, Zhuang, and K. Salomaa in their paper, "The state complexities of some basic operations on regular languages", TCS 125 (1994), 315-328, where the state blow-up for Kleene * is described in detail; it is exponential in the worst-case for languages over 2-letter alphabets or larger, with a bound of the form $3 \cdot 2^{n-2}$. The result for Kleene * was also published (without proof) by Maslov in Dokl. Akad. Nauk SSSR (1970) (and in English in the translation journal Soviet Math. Dokl.)
Evidently the complexity of actually computing the DFA could be exponential in the worst-case, too, then.
-
$\begingroup$ Indeed -- I'm a little surprised that the same paper covered both operations. Very nice! $\endgroup$– AryehMay 16, 2016 at 14:07
-
7$\begingroup$ The title should have tipped you off! $\endgroup$ May 16, 2016 at 16:31