2

私はしばらくこれに苦労していて、何も思い付くことができません。どんなポインタでも本当にありがたいです。

問題は、偶数の長さの単語のみを受け取るすべてのDFAの言語を前提として、それがPであるかどうかを証明することです。

開始状態から受け入れ状態までのすべてのパスを見つけるために、BFS /ダイクストラのアルゴリズムのようなもので特定のDFAを調べるチューリングマシンを作成することを検討しましたが、ループを処理する方法がわかりませんか？

ありがとう！

4

2 に答える 2

1

これには2つの状態しか必要ないようです。

エントリ状態は空の文字列になり、受け入れ状態にもなります。文字列にanythignを追加すると、次の状態に移動します。これを「odd」状態と呼ぶことができますが、受け入れ状態にすることはできません。別の文字列を追加すると、元の状態に戻ります。

言語がPであるかどうかの用語についてはもうわからないと思うので、そこで定義を教えていただければ、これがそれに適合するかどうかを教えていただけますが、これは最も単純なDFAの1つです...

于 2011-12-19T07:29:26.103 に答える
1

最悪の場合、2次式のPにあると思います。DFAの各状態は、4つのパリティ状態を持つことができます

  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状態は最大2回処理され、そのたびに最大でほとんどのsize子に必要なアクションがないかチェックされます。

于 2011-12-19T17:02:16.393 に答える