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

ここでは、言語 L = {ww^r | w ∈ {0, 1}} を受理するチューリングマシンの構築方法について解説します。この言語は、文字「0」と「1」のみで構成される文字列を扱うものです。w は任意の文字列を表し、w^r はその逆順（反転）の文字列を意味します。

例えば、w = 10110 の場合、w^r は 01101 となります。したがって、このチューリングマシンが受理すべき文字列 z は、10110 と 01101 を連結した z = 1011001101 になります。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

1. 先頭の記号を確認する： 文字列の最初の記号を読み取ります。それが「0」であれば「y」に書き換え、「1」であれば「x」に書き換えます。これにより、処理済みの記号と未処理の記号を区別できるようになります。
2. 文字列の末尾へ移動する： テープヘッドを文字列の最後尾まで移動させます。
3. 末尾の記号を照合・置き換える： 末尾の記号が先頭の記号と一致しているかを確認します。一致していれば、先頭と同様に「0」なら「y」、「1」なら「x」に書き換えます。
4. 先頭側に戻って繰り返す： テープヘッドを左端に戻し、次の未処理の記号（直前に置き換えた記号の隣）から同じ手順を繰り返します。

重要なポイント

この言語の性質上、w^r は w の逆順であるため、両者は必ず同じ長さ（同じ記号数）を持つことに注意が必要です。つまり、文字列の前半部分と後半部分は対称的な関係にあります。

そこで、先頭から n 番目の記号を置き換えるたびに、末尾から n 番目に対応する記号も必ず置き換えるという規則を守ることで、文字列が ww^r の形式に一致しているかどうかを正しく判定できます。

すべての記号が正しく対応して置き換えられれば、その文字列は言語 L に属するものとして受理されます。途中で先頭と末尾の記号が一致しない場合は、その文字列は拒否されます。

状態遷移図

以下の状態遷移図は、上記のアルゴリズムを実装したチューリングマシンの動作を視覚的に表したものです。