Computability: Is the language of DFAs that receive even-length words in P?

Question

I've been struggling with this one for a while and am not able to come up with anything. Any pointers would be really appreciated.

The problem is: given the language of all DFAs that receive only words of even-length, prove whether it is in P or not.

I've considered making a turing machine that goes over the given DFA in something like BFS/Dijkstra's algorithm in order to find all the paths from the starting state to the accepting one, but have no idea how to handle loops?

Thanks!

Answer 1

I think it's in P, at worst quadratic. Each state of the DFA can have four parity states

1. unvisited -- state 0
2. known to be reachable in an odd number of steps -- state 1
3. known to be reachable in an even number of steps -- state 2
4. known to be reachable in both, odd and even numbers of steps -- state 3

Mark all states as unvisited, put the starting state in a queue (FIFO, priority, whatever), set its parity state to 2.

child_parity(n)
    switch(n)
        case 0: error 
        case 1: return 2
        case 2: return 1
        case 3: return 3

while(queue not empty)
    dfa_state <- queue
    step_parity = child_parity(dfa_state.parity_state)
    for next_state in dfa_state.children
        old_parity = next_state.parity_state
        next_state.parity_state |= step_parity
        if old_parity != next_state.parity_state // we have learnt something new
            add next_state to queue // remove duplicates if applicable
for as in accept_states
    if as.parity_state & 1 == 1
        return false
return true

Unless I'm overlooking something, each DFA state is treated at most twice, each time checking at most size children for required action.