2
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Indeed -- I'm a little surprised that the same paper covered both operations. Very nice! $\endgroup$ – Aryeh May 16 '16 at 14:07
  • 7
    $\begingroup$ The title should have tipped you off! $\endgroup$ – Jeffrey Shallit May 16 '16 at 16:31

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.