<p>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.) </p>

<p>Evidently the complexity of actually computing the DFA could be exponential in the worst-case, too, then.</p>

CC BY-SA 3.0
2016-05-16T14:07:38.803Z
Indeed -- I'm a little surprised that the same paper covered both operations. Very nice!
Aryeh
CC BY-SA 3.0
2016-05-16T16:31:17.560Z
The title should have tipped you off!
Jeffrey Shallit
CC BY-SA 3.0
2016-05-16T13:17:16.150Z
2016-05-16T13:17:16.150Z
Jeffrey Shallit
<p>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?</p>

CC BY-SA 3.0
2016-05-16T11:37:29.463Z
prompted by this question, which, while poorly phrased, contains a valid core I think http://cstheory.stackexchange.com/questions/34763/how-to-find-the-closure-of-a-dfa
Aryeh
<automata-theory>
Kleene closure of DFA
Aryeh
# Kleene closure of DFA

(Asked by: username_0 on 2016-05-16)

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?

**Tags:** automata-theory

> **Comments:**
> **username_0**: prompted by this question, which, while poorly phrased, contains a valid core I think http://cstheory.stackexchange.com/questions/34763/how-to-find-the-closure-of-a-dfa  

---

## 1 answers

### Answer by username_1 on 2016-05-16. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_0**: Indeed -- I'm a little surprised that the same paper covered both operations. Very nice!  
> **username_1**: The title should have tipped you off!  

---

