[Solved]: Can we check in polynomial time if the language of a DFA is closed against Kleene star?

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 $qin F$, where $A_q = (Q,q,F,delta)$. In order to check whether this holds, you can compute the product $Atimes A$ and check whether the subset $Ftimes(Qsetminus 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 $Atimes A = (Qtimes Q, (q_0,q_0), Ftimes F, delta’)$, where

• the set of states $Qtimes Q$ consists of all pairs $(q_1,q_2)$ with $q_1,q_2in 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 $qin 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 $Ftimes(Qsetminus F)$ being unreachable from $(q_0,q)$ in $Atimes 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 $qin F$ and $rnotin 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_2notin 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_3notin 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 $Ftimes(Qsetminus F)$.

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