2

我一直在努力解决这个问题，但无法提出任何建议。任何指针将不胜感激。

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

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

谢谢！

4

2 回答 2

1

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

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

我想我不确定一种语言是否在 P 中的术语，所以如果你在那里给我一个定义，我可以告诉你这是否适合它，但这是最简单的 DFA 之一......

于 2011-12-19T07:29:26.103 回答
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子项以执行所需的操作。

于 2011-12-19T17:02:16.393 回答