# Is the language in class P

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)*}

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.