言語 L = {ww | w ∈ {0,1}} を認識するチューリングマシンの構築方法

言語 L = {ww | w ∈ {0,1}} とは

ここでは、言語 L = {ww | w ∈ {0,1}} を認識するチューリングマシンの構築方法を解説します。この言語は、記号 0 と 1 のみから構成される文字列 w が2回繰り返された形(ww)の集合を表しています。例えば、w = 10110 の場合、チューリングマシンが受理すべき文字列は z = 1011010110 となります。

解法のアプローチ

ステップ1:文字列の中点を見つける

まず最初の目標は、文字列の中点を特定することです。そのために、左端の記号(0 なら x、1 なら y)と右端の記号(0 なら x、1 なら y)を順次変換しながら、内側へ向かって処理を進めます。この操作を繰り返し、すべての 0 と 1 が x と y に変換された時点で、処理ヘッドは文字列の中点に到達しています。これで第一の目標が完了です。

ステップ2:前半部分を元の記号に戻す

次に、中点より左側にある x と y を、すべて 0 と 1 に戻します。これにより、文字列の前半部分は 0 と 1 の形式になり、後半部分は x と y の形式のまま残ります。

ステップ3:対応関係の照合

続いて、再び文字列の先頭から処理を開始します。先頭に 0 があればそれを x に変換し、後半部分に到達するまで右へ移動します。後半部分で x が見つかれば、それを空白(B)に変換します。その後、x または y が見つかるまで左へ戻り、その右隣の 0 または 1 をそれぞれ x または y に変換するとともに、後半部分の対応する x または y を空白(B)に変換します。

ステップ4:繰り返し処理と受理判定

この操作を、文字列の左半分の記号がすべて x と y に、右半分の記号がすべて空白(B)に変換されるまで繰り返します。以下の場合、文字列は受理されません。

• 片方の半分の変換が完了しても、もう片方の半分に未変換の記号が残っている場合
• 前半部分の 0 または 1 に対応する x または y が、後半部分で見つからない場合

状態遷移図

以下の状態遷移図は、上記のアルゴリズムを実装したチューリングマシンの動作を表しています。