# Can we check in polynomial time if the language of a DFA is closed against Kleene star?

I was wondering if there is a polynomial time algorithm to test whether a DFA recognizes a star closed language ( which is if $A=A^*$). I think that yes, but I do not have an idea to do it.

• Polynomial in which parameter? – J.-E. Pin Apr 28 '15 at 0:15
• @J.-E.Pin, probably in the size of the DFA's description. At least that would be the usual measure for these kinds of problems. – Rick Decker Apr 28 '15 at 0:39
• See also a different but related question on cstheory: cstheory.stackexchange.com/questions/4254/…. – Yuval Filmus Apr 28 '15 at 17:58
• big-O @J.-E.Pin – Optimistic Apr 29 '15 at 0:17

Assuming your DFA $A = (Q,q_0,F,\delta)$ is minimal, here is one approach:

$L(A) = L(A)^*$ iff $q_0$ is accepting, and adding $\epsilon$-transitions from each accepting state $q$ to $q_0$ does not change the language; the latter is true iff $L(A)\subseteq L(A_q)$ for each $q\in F$, where $A_q = (Q,q,F,\delta)$.

In order to check whether this holds, you can compute the product $A\times A$ and check whether the subset $F\times(Q\setminus F)$ is unreachable from $\{q_0\}\times F$, which you can do in polynomial time. In some more detail:

The product automaton has the form $A\times A = (Q\times Q, (q_0,q_0), F\times F, \delta')$, where

• the set of states $Q\times Q$ consists of all pairs $(q_1,q_2)$ with $q_1,q_2\in Q$;
• the initial state is the pair $(q_0,q_0)$ (though we won't be needing it for our purposes);
• the accepting states are all pairs $(q_1,q_2)$ where both $q_1,q_2$ are accepting in $A$;
• the transition function $\delta'$ applies the original transition function to both components of a pair, i.e. $\delta'((q_1,q_2),a) = (\delta(q_1,a),\delta(q_2,a))$.

In order to check whether $L(A)\subseteq L(A_q)$ for some $q\in F$, we start from the pair $(q_0,q)$; there should be no word $w$ such that $\delta(q_0,w)\in F$ and $\delta(q,w)\notin F$, which is equivalent to the set $F\times(Q\setminus F)$ being unreachable from $(q_0,q)$ in $A\times A$.

For example, consider the language given by the regular expression $(a + ab + ba)^*$ mentioned earlier by J-E. Pin. It is accepted by the automaton $A=(Q,q_0,F,\delta)$, where

• $Q=\{q_0,q_1,q_2,q_3\}$,
• $F=\{q_0,q_1\}$,
• $\delta = \{(q_0,a,q_1),(q_1,a,q_1),(q_2,a,q_0),(q_3,a,q_3),(q_0,b,q_2),(q_1,b,q_0),(q_2,b,q_3),(q_3,b,q_3)\}$.

The only pair we have to check is $(q_0,q_1)$; exploring the states we can reach from it, we get:

• $\delta'((q_0,q_1),a) = (q_1,q_1)$ - note that both components are the same; since $A$ is deterministic, this will be also be the case for all states reachable from here, in particular we will never reach any $(q,r)$ with $q\in F$ and $r\notin F$. We therefore don't need to explore this branch any further.
• $\delta'((q_0,q_1),b) = (q_2,q_0)$. Fine because $q_2\notin F$.
• $\delta'((q_2,q_0),a) = (q_0,q_1)$. Back to where we started.
• $\delta'((q_2,q_0),b) = (q_3,q_2)$. Not only is $q_3\notin F$, but it is a trap state, i.e. all states we can reach from here are of the form $(q_3,q)$ and therefore not in $F\times(Q\setminus F)$.

Since we cannot reach $F\times (Q\setminus F)$ from $(q_0,q_1)$, we now know $L(A)\subseteq L(A_q)$ and therefore $L(A) = L(A)^*$.

• Is there another way for checking than computing product of A * A? and check whether the subset F×(Q∖F) is unreachable from {q0}×F? – Optimistic Apr 29 '15 at 11:36
• There might be - but how different would a solution have to be to count as "another way"? Many "different" approaches would be essentially the same thing in disguise. – Klaus Draeger Apr 29 '15 at 12:04
• Ok, why you compute the product A×A? do you mean Aq? and what is the subset F×(Q∖F) ?I did not understand. – Optimistic Apr 29 '15 at 12:29
• Just to be sure - is it the notation (cartesian product $S\times T$, set difference $S\setminus T,\dots$) you are unfamiliar with? – Klaus Draeger Apr 29 '15 at 15:48