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.
-
1$\begingroup$ Polynomial in which parameter? $\endgroup$ – J.-E. Pin Apr 28 '15 at 0:15
-
1$\begingroup$ @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. $\endgroup$ – Rick Decker Apr 28 '15 at 0:39
-
$\begingroup$ See also a different but related question on cstheory: cstheory.stackexchange.com/questions/4254/…. $\endgroup$ – Yuval Filmus Apr 28 '15 at 17:58
-
$\begingroup$ big-O @J.-E.Pin $\endgroup$ – 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)^*$.
-
$\begingroup$ 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? $\endgroup$ – Optimistic Apr 29 '15 at 11:36
-
$\begingroup$ 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. $\endgroup$ – Klaus Draeger Apr 29 '15 at 12:04
-
$\begingroup$ Ok, why you compute the product A×A? do you mean Aq? and what is the subset F×(Q∖F) ?I did not understand. $\endgroup$ – Optimistic Apr 29 '15 at 12:29
-
$\begingroup$ Just to be sure - is it the notation (cartesian product $S\times T$, set difference $S\setminus T,\dots$) you are unfamiliar with? $\endgroup$ – Klaus Draeger Apr 29 '15 at 15:48
-
1$\begingroup$ @Macrophage A problem with that approach is that by construction, $L(A_\epsilon)\supseteq L(A)$, since $A_\epsilon$ has all the states and transitions of $A$ plus the extra $\epsilon$-transitions. The language of the intersection will therefore always be equal to $L(A)$. $\endgroup$ – Klaus Draeger Nov 28 '20 at 19:43