5

w^R は w の逆で、w は {0, 1}* です。そのため、TM は単語の後にこの単語の逆の単語が続き、その単語が続く単語を決定する必要があります。私は答えが欲しいのではなく、リードが始まり、正しい軌道に乗ることを望んでいます.

4

3 に答える 3

6

しばらく時間が経ち、答えはおそらくもう必要ないので、ある言語がチューリングマシンによってどのように認識されるかの例を探している将来の学生のために解決策を提案すると思います.

これがアイデアです。テープのアルファベット {0, 1, a, b, c, d} として、ww^R w を認識する単一テープの単一無限テープ チューリング マシンを作成します。マシンは 5 つのフェーズで動作します。

  1. プレフィックス ww^R の 0 と 1 を a と b に置き換えます。
  2. ww^R が回文かどうかを確認します。
  3. テープを元の状態に戻します。
  4. サフィックス w^R w の 0 と 1 を c と d に置き換えます。
  5. w^R が回文かどうかを確認します。

これは、この言語を認識するためのチューリング マシンが存在することを示す簡単な (つまり、私が理解できる) 方法の 1 つに過ぎないことに注意してください。当然のことながら、チューリングと同等の計算システムでこれを解決するアルゴリズムが存在することを示すことは、同様に優れています (TM が存在することを証明します) ... それでも、これはそのような TM の 1 つの構築の概要を示しています。また、この問題を解決するための、より単純で効率的、またはより直感的な TM があるかもしれないことにも注意してください。繰り返しますが、これは 1 つのアプローチにすぎません。

ステップ 1 は次のように機能します。

  • 前提条件: テープは空白で始まり、(0+1)* に任意の文字列が含まれ、その後に空白の正方形の無限の文字列が続きます。

  • 事後条件: テープが空の場合、または長さが 3 の倍数でない場合は停止します。それ以外の場合、テープは空白で始まり、(a+b)^2n (c+d)^n が続き、その後に空白の無限の文字列が続きます。

    1. 右に移動します。
    2. 空の場合、受け入れを停止します。それ以外の場合は、空のテープの正方形が見つかるまで右にスキャンしてから、左に移動します。
    3. テープを 0 の場合は c に、1 の場合は d に変更します。
    4. 空のテープの正方形が見つかるまで左にスキャンします。右に動く。
    5. テープが 0 または 1 の場合は、a または b に変更してから右に移動します。テープが c または d の場合、リジェクトを停止します。
    6. テープが 0 または 1 の場合は、a または b に変更してから右に移動します。テープが c または d の場合、リジェクトを停止します。
    7. テープが c または d の場合は、テープの先頭までスキャンして手順 2 に進みます。それ以外の場合は、c または d まで右にスキャンしてから、左に移動します。
    8. テープを 0 の場合は c に、1 の場合は d に変更します。
    9. a または b が見つかるまで左にスキャンします。右に動く。
    10. 4から繰り返します。

ステップ 2 は次のように機能します。

  • 前提条件: テープは空白で始まり、(a+b)^2n (c+d)^n が続き、その後に空白の無限の文字列が続きます。

  • 事後条件: プレフィックス (a+b)^2n が回文でない場合は停止します。それ以外の場合、テープは D (c+d)^3n D* のような状態のままになります。

    1. 右に動く。
    2. テープが a (または b) の場合、右に移動します。テープが c または d の場合は、テープの先頭に移動してから、手順 3 に進みます。
    3. テープが c、d、またはブランクの場合は、リジェクトを停止します。それ以外の場合は、ac、d、または空白が見つかるまで右にスキャンします。左に移動します。
    4. テープが ab (または a) の場合、リジェクトを停止します。それ以外の場合は、これを ac (または d) に変更し、空白の ac または d が表示されるまで左にスキャンします。右に動く。a (または b) を c (または d) に変更します。右に動く。
    5. 手順 2 から繰り返します。

ステップ3は次のように機能します

  • 前提条件: テープは D (c+d)^3n D*

  • 事後条件: テープは D (0+1)^3n D* です

    1. 右に動く。
    2. テープがcなら0を書いて右へ移動。テープが d の場合、1 を書き、右に移動します。テープがブランクの場合は、テープの最後にある最初のブランク スペースに移動し、手順 4 に進みます。
    3. 手順 2 を繰り返します。

ステップ 4 と 5 はステップ 1 と 2 と同じように機能しますが、逆方向に作業する点が異なります (テープは D (c+d)^n (a+b)^2n D* のようになり、(a +b)^2n の部分は回文です。

これらの両方のテストに合格する文字列は、ww^R w の形式である必要があります。ここで、w は (0+1)* の中にあります。

于 2011-10-12T20:51:15.383 に答える
2

ヒントとして、 ww R w の長さは n に対して 3n でなければならないことに注意してください(各文字が正確に 3 回出現するため)。したがって、何らかの方法で文字列の長さを数え、これを使用して 3 つの文字列の境界がどこにあるかを判断し、3 つの部分がすべて適切な構成になっていることを確認することで機能するチューリング マシンを構築できます。3文字の倍数を数えられない場合は、すぐに拒否できます。

許可されている TM の種類によっては、マルチトラックまたはマルチテープのチューリング マシンを使用すると、文字に追加情報をマークアップできるため、これが最も簡単な場合があります。

お役に立てれば！

于 2011-10-03T03:11:15.093 に答える