【C++】L = {aⁿbᵐaⁿ⁺ᵐ}（n, m ≥ 1）を受理するチューリングマシンの構築方法

チューリングマシン（Turing Machine）とは

チューリングマシンは、0型文法（タイプ0文法）から生成される言語の語を受理するために用いられる装置です。チューリングマシン（TM）は、セルに区切られた無限長のテープからなる数学的モデルであり、このテープに入力が与えられます。TMは入力テープを読み取るヘッドを備え、状態レジスタがマシンの現在の状態を保持します。入力記号を読み込むと、その記号は別の記号に置き換えられ、内部状態が変化し、ヘッドは左右いずれかのセルへ移動します。TMが最終状態に到達すれば入力文字列は受理され、到達できなければ拒否されます。

TMは次の7つ組（Q, X, Σ, δ, q₀, B, F）として形式的に定義できます。

• Q：状態の有限集合
• X：テープアルファベット
• Σ：入力アルファベット
• δ：遷移関数。δ : Q × X → Q × X × {左シフト, 右シフト}
• q₀：初期状態
• B：空白記号
• F：最終状態の集合

構築対象となる言語

今回の目標は、次の言語を受理するチューリングマシンTMを構築することです。

L = { aⁿ bᵐ a⁽ⁿ⁺ᵐ⁾ | n, m ≥ 1 }

受理される語の例

• abaa（n=1, m=1）
• aabaaa（n=2, m=1）
• abbaaa（n=1, m=2）
• aaabaaaa（n=3, m=1）

つまり、「n個のa ＋ m個のb ＋ (n+m)個のa」という並びの文字列です（n, m ≥ 1）。したがって、文字列に含まれるaの最小個数は常に3、bの最小個数は常に1となります（n=m=1のとき）。

アプローチの概要

マシンはまず、先頭のn個のaとそれに続くm個のbを受け入れます。その後、後半のaに出会うたびに、それまでに読み込んだbやaを順番に消去していきます。最終的に新しいaが現れなくなり、ヘッドが先頭の入力文字まで戻った時点で、すべての文字が正しく処理されたことになります。以下、具体的な入力文字列に対する動作を段階的に確認しましょう。

状態q₀からの遷移

• δ(q₀, a) → (q₁, x, R)：状態q₀で読み取った文字が「a」の場合、状態q₁へ遷移し、その文字を「x」に書き換えて右へ移動し、文字列の次の文字を指します。
  例：aabaaa → xabaaa（先頭の文字がxになり、ヘッドは次のaへ右移動）
• δ(q₀, b) → (q₃, x, R)：状態q₀で読み取った文字が「b」の場合、状態q₃へ遷移し、その文字を「x」に書き換えて右へ移動します。
  例：babaaa… → xabaaa…（先頭の文字がxになり、ヘッドは次の文字へ右移動）

ここで「x」は、先頭の文字（処理済みである印）を表すために使用します。

状態q₁からの遷移

• δ(q₁, a) → (q₁, a, R)：状態q₁で読み取った文字が「a」の場合、状態q₁にとどまり、右へ移動して次の文字を指します。
  例：xaabaaa… → xaabaaa…（残りのaはそのまま右へ進む）
• δ(q₁, b) → (q₂, b, R)：状態q₁で読み取った文字が「b」の場合、状態q₂へ遷移し、右へ移動します。
  例：xaabaaa… → xaabaaa…（残りのbもそのまま右へ進む）

状態q₂からの遷移

• δ(q₂, b) → (q₂, b, R)：状態q₂で読み取った文字が「b」の場合、状態q₂にとどまり、右へ移動します。
  例：xaabbbaaa… → xaabbbaaa…（残りのbはそのまま右へ進む）
• δ(q₂, z) → (q₂, z, R)：状態q₂で読み取った文字が「z」の場合、状態q₂にとどまり、右へ移動します。
  例：xaabaazz… → xaabaazz…（残りのzはそのまま右へ進む）
• δ(q₂, a) → (q₃, z, L)：状態q₂で読み取った文字が「a」の場合、それを「z」に書き換え、状態q₃へ遷移して左へ移動します。
  例：xaabaazz… → xaabazzz…（aをzに置き換えて左移動）

状態q₃からの遷移

• δ(q₃, z) → (q₃, z, L)：状態q₃で読み取った文字が「z」の場合、状態q₃にとどまり、左へ移動します。
  例：xaabzzzz… → xaabzzzz…（zはそのまま左へ進む）
• δ(q₃, b) → (q₂, z, R)：状態q₃で読み取った文字が「b」の場合、それを「z」に書き換え、状態q₂へ遷移して右へ移動します。これによりbがすべて置き換えられていきます。
  例：xaabzzzz… → xaazzzzz…（bをzに置き換えて右移動）
• δ(q₃, a) → (q₂, z, R)：状態q₃で読み取った文字が「a」の場合、それを「z」に書き換え、状態q₂へ遷移して右へ移動します。これによりaがすべて置き換えられていきます。
  例：xaazzzz… → xaazzzzz…（aをzに置き換えて右移動）
• δ(q₃, x) → (q₄, z, R)：状態q₃で読み取った文字が「x」の場合、それを「z」に書き換え、状態q₄へ遷移して右へ移動します。ここで先頭の記号に到達したことになります。
  例：xzzzzzzz… → zzzzzzzz…（xをzに置き換えて右移動）

状態q₄からの遷移

• δ(q₄, z) → (q₄, z, R)：状態q₄で読み取った文字が「z」の場合、状態q₄にとどまり、右へ移動します。この時点ですべての文字がzになっています。
  例：zzzzzzzz… → zzzzzzzz…（すべてのzはそのまま右へ進む）
• δ(q₄, $) → (qf, $, R)：状態q₄で読み取る文字が残っておらず、文字列の末尾を表す「$」に到達した場合、最終状態qfへ遷移します。これは文字列が受理されたことを意味します。
  例：zzzzzzzz$ → zzzzzzzz$（末尾の$では何もせず最終状態へ）

下図はこのチューリングマシンの状態遷移図です。

動作のポイント

このマシンでは、記号「x」が文字列の先頭位置の目印、「z」がすでに処理済み（対応関係が確認済み）の記号を表します。後半のaを1つ読むごとに、前半のaまたはbを1つずつzへ置き換えていくことで、後半のaの個数が前半のaとbの合計（n+m）と一致しているかを検証しています。すべての記号がzに置き換わり、余りも不足もなければ文字列は受理されます。

実行例

入力

aabaaa
q0: aabaaa → q1: xabaaa → q1: xabaaa → q2: xabaaa → q3: xabzaa → q2: xazzaa
q2: xazzaa → q3: xazzza → q3: xazzza → q3: xazzza → q2: xzzzzza → q2: xzzzzza
q2: xzzzzza → q2: xzzzzza → q2: xzzzzza → q2: xzzzzzz → q3: xzzzzzz……..
q3: xzzzzzz → q3: xzzzzzz → q4: zzzzzzz → q4: zzzzzzz…….. → qf: zzzzzzz$

最終状態qfに到達したため、入力「aabaaa」（n=2, m=1）は正しく受理されました。