4
$\begingroup$

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.

$\endgroup$
  • 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
6
$\begingroup$

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

$\endgroup$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.