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

Question

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.

Answer 1

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)^*$.