言語 L = {0ⁿ1ⁿ2ⁿ | n ≥ 1} を認識するチューリングマシンの構築方法

本記事では、言語 L = {0ⁿ1ⁿ2ⁿ | n ≥ 1} を認識するチューリングマシンの構築方法について解説します。この言語は、記号「0」「1」「2」の3種類のみで構成され、それぞれの記号が同じ個数ずつ順番に並んだ文字列の集合を表します。例えば、w = 000111222 のような文字列は、0・1・2がそれぞれ3個ずつ対応しているため、チューリングマシンによって受理されます。

解法のアプローチ

この問題を解くには、先頭から順に記号を別の記号へ置き換えていく「マーキング方式」を採用します。具体的な手順は以下の通りです。

1. まず、先頭の「0」を1つ選んで「x」に置き換えます。
2. 次に、右方向へヘッドを移動し続け、「1」を見つけたらそれを「y」に置き換えます。
3. さらに右へ移動を続け、「2」を見つけたら「z」に置き換え、今度は左方向へ移動します。
4. 左へ移動し続けて「x」を見つけたら、1つ右へ移動し、上記と同じ手順を繰り返します。

受理条件の判定

処理を進めていくと、「x」の直後に「y」が続く状態が出現します。この時点では、右方向へ移動しながら、残りのすべての「1」と「2」が「y」と「z」に正しく変換済みであるかを確認していきます。

• 未変換の「1」や「2」が残っている場合は、0・1・2の個数が一致していないことを意味するため、その文字列は受理されません(拒否されます)。
• 最後にブランク記号「$」に到達できた場合は、すべての記号が正しく対応付けられたことになるため、その文字列は受理されます。

状態遷移図

以下の状態遷移図は、上述のアルゴリズムを実現するチューリングマシンの各状態と遷移を視覚的に表したものです。各状態がどの記号を読み込んだときにどのように動作するかを追うことで、マシン全体の挙動を理解できます。