可计算性：接收 P 中偶数长度单词的 DFA 语言是吗？

Question

我已经在这个问题上苦苦挣扎了一段时间，但无法想出任何办法。任何指点将非常感激。

问题是：给定所有仅接收偶数长度单词的 DFA 的语言，证明它是否在 P 中。

我考虑过制作一台图灵机，用 BFS/Dijkstra 算法之类的算法遍历给定的 DFA，以便找到从起始状态到接受状态的所有路径，但不知道如何处理循环？

谢谢！

Answer 1

我认为它在 P 中，最坏的是二次。 DFA 的每个状态可以有四个

1. 未访问的奇偶状态 - 状态 0
2. 已知可在奇数步中到达 - 状态 1
3. 已知可在偶数步中到达 - 状态 2
4. 已知在两者中均可到达，奇数和偶数步数 -- 状态 3

将所有状态标记为未访问，将起始状态放入队列中（FIFO、优先级等），将其奇偶校验状态设置为 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

除非我忽略了某些内容，否则每个 DFA 状态都会被处理最多两次，每次最多检查 size 个子项是否需要执行操作。

Answer 2

看起来这只需要两个状态。

您的输入状态将是空字符串，并且也将是接受状态。将任何内容添加到字符串中都会将其移动到下一个状态，我们可以将其称为“奇数”状态，而不是使其成为接受状态。添加另一个字符串会让我们回到原始状态。

我想我不再确定术语是否属于 P 语言，所以如果你给我一个定义，我可以告诉你这是否合适，但这是最简单的 DFA 之一......