1
$\begingroup$

So class P is the class of languages that are decidable in polynomial time on a deterministic single-tape TM.

I can show that the decider for a language L* runs in polynomial time.

So is it true that this language in class P? STARCLOSED DFA = { | A is a DFA, and L(A) = L(A)*}

$\endgroup$

1 Answer 1

3
$\begingroup$

A language L is equal to its Kleene closure if and only if L contains ε and L = L^2. So in a sense, this problem boils down to testing whether those two conditions are true. The test for whether L contains ε is pretty easy to accomplish - just see if A's start state is accepting. The trickier part is seeing whether L = L^2.

If you already know that ε ∈ L, then L ⊆ L^2, so the only way that L isn't equal to L^2 is if there's a string in L^2 that isn't in L. This is something we can test in polynomial time, as follows:

  1. Construct an NFA for L^2 by applying the concatenation construction to A and itself. Call the resulting automaton B.

  2. Take the cross product of B and the automaton formed by flipping the accept and reject states of A. Running this automaton corresponds to simultaneously running A and B, with the accepting states corresponding to executions that lead to an accepting state in B and a rejecting state in A.

  3. Run a DFS over this net automaton to find an accepting state. If one exists and is reachable, there's a string in L^2 that isn't in L, and otherwise every string in L^2 is in L.

Step (1) takes polynomial time and builds an automaton with 2n states, where n is the number of states in the original automaton A, since we're just duplicating the states in A and adding in some new transitions. Step (2) builds an automaton with 2n^2 states, and the DFS in step (3) runs in time polynomial in n.

Overall, this construction runs in polynomial time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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