L = {aⁱbʲcᵏ | i × j = k、i, j, k ≥ 1} を受理するチューリングマシンの構築方法

本記事では、言語 L = {aⁱbʲcᵏ | i × j = k、i, j, k ≥ 1} に対応するチューリングマシンの構築方法を解説します。この言語は、A・B・C の3種類の記号のみからなる文字列のうち、「A の個数(i)と B の個数(j)の積が C の個数(k)と一致する」という条件を満たすものの集合を表しています。

受理される文字列の例

例えば、w = AABBBBCCCCCCCC という入力文字列を考えてみましょう。この場合、A が2個、B が4個、C が8個含まれており、2 × 4 = 8 という関係が成立しているため、このチューリングマシンはこの文字列を受理します。

構築のアプローチ

この問題を解決するために、テープ上の記号を X・Y・Z へ段階的に書き換えながら積の対応関係を検証する、以下の手順を採用します。

• まず、先頭の A を X に書き換えて右へ移動します。その後、残りの A をすべて読み飛ばしながら右へ進みます。

• ヘッドが最初の B に到達したら、その B を Y に書き換えます。さらに右へ移動して途中の B を読み飛ばし、書き換えた B に対応する C を1つ Z に書き換えてから左へ移動します。

• 次に、左方向へ移動し、途中の Z と B をすべて読み飛ばします。

• ポインタが直前に書き換えた Y に到達したら、右へ移動します。

• ポインタが B を指している場合は、手順2〜4を繰り返します。一方、ポインタが Z を指している場合は、左へ移動しながらすべての Y を B に戻し、A は読み飛ばします。

• ポインタが最も最近書き換えた X に到達したら、右へ移動します。

• ポインタがまだ A を指している場合は、上記の手順をすべて繰り返します。ヘッドが Y の位置にある場合は、右へ移動しながらすべての Y と Z を読み飛ばします。

• 最後に、$ 記号(右端のマーカー)に到達したら左へ移動します。これにより、文字列は受理されたことになります。

状態遷移図

以下の状態遷移図は、上述の手順に基づいて設計されたチューリングマシンの全体像を示しています。