チューリングマシンによる `a^n b^n` 形式文字列の認識:シミュレーターで追う動作ステップ
はじめに
計算機科学において、言語の認識能力は重要なテーマです。特に、あるクラスの言語を認識できるか否かは、計算モデルの能力を示す指標となります。有限オートマトンは非常にシンプルな計算モデルですが、テープのような記憶媒体を持たないため、文脈自由言語の一部を認識できません。その代表的な例が、a
がn個続き、その後にb
がn個続く形式の文字列からなる言語 { a^n b^n | n >= 0 }
です(例: "", "ab", "aabb", "aaabbb", ...)。
この a^n b^n
形式の文字列を認識するには、「a
の個数とb
の個数が一致しているか」を記憶し、照合する必要があります。チューリングマシンはテープという記憶媒体を持つため、このような処理が可能です。
本記事では、チューリングマシンがどのようにして a^n b^n
形式の文字列を認識するのか、その基本的なアルゴリズムと状態遷移を解説します。そして、シミュレーター上でその動作をステップバイステップで追体験することで、理論的な仕組みと具体的な機械の動作との対応を深く理解することを目的とします。
a^n b^n
言語の定義とチューリングマシンの役割
a^n b^n
言語とは、アルファベット {a, b}
上の文字列で、0個以上の a
の並びの直後に、それと同数の b
の並びが続くものです。形式的に { a^n b^n | n >= 0 }
と定義されます。
有限オートマトンは入力文字列を一度だけ順方向に読むだけで、過去に読んだ記号の「個数」を正確に記憶し続けることはできません。状態数は有限であるため、任意の数の a
を数えることは原理的に不可能です。
一方、チューリングマシンは無限のテープを持ち、ヘッドを左右に移動させてテープ上の記号を読み書きできます。この能力を利用することで、入力文字列を複数回走査したり、テープ上の記号を書き換えて目印をつけたりすることが可能となり、a
と b
の個数を照合する処理を実現できます。
a^n b^n
認識アルゴリズムの概要
チューリングマシンで a^n b^n
形式の文字列を認識する基本的なアルゴリズムは、以下のような手順で実現できます。
- テープの入力文字列を左から右へ走査し、まだ処理していない最初の
a
を探します。 - 最初の
a
を見つけたら、そのa
を別の記号(例:X
)に書き換えます。これは、「このa
は処理済みである」という目印になります。 - ヘッドを左方向に戻し、処理済みの
a
に対応する最初のb
を探します。 - 最初の
b
を見つけたら、そのb
を別の記号(例:Y
)に書き換えます。これは、「このb
は処理済みであり、対応するa
が存在した」という目印になります。 - ヘッドを左方向に戻し、まだ処理していない次の
a
を探すために、先頭(または処理済みのX
の直後)に戻ります。 - 上記の手順1〜5を、処理すべき
a
またはb
がなくなるまで繰り返します。 - 全ての
a
とb
をX
とY
に置き換え終わった後、テープ上にX
とY
以外の入力記号(a
やb
)が残っていないか確認します。残りが全てX
とY
、そして右側に広がる空白だけであれば、入力文字列はa^n b^n
形式であり、チューリングマシンは受理状態へ遷移して停止します。それ以外の場合は非受理となります。
このアルゴリズムでは、a
を1つ処理するたびにそれに対応する b
を1つ処理するというサイクルを繰り返すことで、最終的に a
と b
の個数が一致しているかどうかを確認しています。テープへの書き換えとヘッドの往復移動が、この「対応付け」と「個数の一致確認」を可能にしています。
シミュレーターで追う具体的な動作ステップ
それでは、具体的な入力文字列 aabb
を例に、上記のアルゴリズムに基づくチューリングマシンの動作をシミュレーター上で追ってみましょう。チューリングマシンは以下の状態と遷移ルールを持つとします。初期状態は q_start
、受理状態は q_accept
、非受理状態は q_reject
とします。テープの空白記号は _
とします。
状態と遷移ルール
q_start
(初期状態): 未処理のa
を探し右へ走査。a
->X
, R,q_find_b
(最初のa
を見つけ、X
に置き換えてb
を探しへ)Y
->Y
, R,q_check_all_y
(a
がなくなりY
だけになったら確認へ)_
->_
, R,q_accept
(空文字列ε
は受理)X
->X
, R,q_start
(処理済みのX
をスキップ)b
->b
, R,q_reject
(a
より先にb
が出現した場合など)
q_find_b
:X
に対応するb
を探し右へ走査。a
->a
, R,q_find_b
(a
をスキップ)Y
->Y
, R,q_find_b
(Y
をスキップ)b
->Y
, L,q_find_x
(b
を見つけY
に置き換え、対応するX
を探しへ)X
->X
, R,q_reject
(b
が見つからずX
に到達 =b
が少ない)_
->_
, R,q_reject
(b
が見つからず終端 =b
が少ない)
q_find_x
:Y
に対応するX
を探し左へ走査。a
->a
, L,q_find_x
(a
をスキップ)Y
->Y
, L,q_find_x
(Y
をスキップ)X
->X
, R,q_start
(X
を見つけたら、次のa
を探すために右へ移動しq_start
へ)_
->_
, R,q_start
(左端(空白)に到達したら、次のa
を探すために右へ移動しq_start
へ)b
->b
, L,q_reject
(Y
以外を見つけた場合など)
q_check_all_y
: 全てのa
処理後、残りがY
と空白のみか確認。Y
->Y
, R,q_check_all_y
(Y
をスキップ)_
->_
, R,q_accept
(全てY
と空白だった、受理)X
->X
, R,q_reject
(Y
以外(X
)が残っていた =a
が多い)a
->a
, R,q_reject
(未処理のa
が残っていた =a
が多い)b
->b
, R,q_reject
(未処理のb
が残っていた =b
が多い)
q_accept
: 受理状態。停止。q_reject
: 非受理状態。停止。
入力: aabb
での動作追跡
- 初期状態: 状態
q_start
、テープ... _ [a] a b b _ ...
、ヘッドは最初のa
の位置。- シミュレーター表示例: State:
q_start
, Tape:... _ [a] a b b _ ...
(括弧はヘッド位置)
- シミュレーター表示例: State:
- ステップ 1: State:
q_start
, Head:a
. Rule:a
->X
, R,q_find_b
.- 動作:
a
をX
に書き換え、ヘッド右移動、状態q_find_b
。 - シミュレーター: State:
q_find_b
, Tape:... _ X [a] b b _ ...
- 動作:
- ステップ 2: State:
q_find_b
, Head:a
. Rule:a
->a
, R,q_find_b
.- 動作: ヘッド右移動、状態
q_find_b
のまま。 - シミュレーター: State:
q_find_b
, Tape:... _ X a [b] b _ ...
- 動作: ヘッド右移動、状態
- ステップ 3: State:
q_find_b
, Head:b
. Rule:b
->Y
, L,q_find_x
.- 動作:
b
をY
に書き換え、ヘッド左移動、状態q_find_x
。 - シミュレーター: State:
q_find_x
, Tape:... _ X [a] Y b _ ...
- 動作:
- ステップ 4: State:
q_find_x
, Head:a
. Rule:a
->a
, L,q_find_x
.- 動作: ヘッド左移動、状態
q_find_x
のまま。 - シミュレーター: State:
q_find_x
, Tape:... _ [X] a Y b _ ...
- 動作: ヘッド左移動、状態
- ステップ 5: State:
q_find_x
, Head:X
. Rule:X
->X
, R,q_start
.- 動作: ヘッド右移動、状態
q_start
。次のa
を探すサイクルへ。 - シミュレーター: State:
q_start
, Tape:... _ X [a] Y b _ ...
- 動作: ヘッド右移動、状態
- ステップ 6: State:
q_start
, Head:a
. Rule:a
->X
, R,q_find_b
.- 動作:
a
をX
に書き換え、ヘッド右移動、状態q_find_b
。 - シミュレーター: State:
q_find_b
, Tape:... _ X X [Y] b _ ...
- 動作:
- ステップ 7: State:
q_find_b
, Head:Y
. Rule:Y
->Y
, R,q_find_b
.- 動作: ヘッド右移動、状態
q_find_b
のまま。 - シミュレーター: State:
q_find_b
, Tape:... _ X X Y [b] _ ...
- 動作: ヘッド右移動、状態
- ステップ 8: State:
q_find_b
, Head:b
. Rule:b
->Y
, L,q_find_x
.- 動作:
b
をY
に書き換え、ヘッド左移動、状態q_find_x
。 - シミュレーター: State:
q_find_x
, Tape:... _ X X [Y] Y _ ...
- 動作:
- ステップ 9: State:
q_find_x
, Head:Y
. Rule:Y
->Y
, L,q_find_x
.- 動作: ヘッド左移動、状態
q_find_x
のまま。 - シミュレーター: State:
q_find_x
, Tape:... _ X [X] Y Y _ ...
- 動作: ヘッド左移動、状態
- ステップ 10: State:
q_find_x
, Head:X
. Rule:X
->X
, R,q_start
.- 動作: ヘッド右移動、状態
q_start
。次のa
を探すサイクルへ。 - シミュレーター: State:
q_start
, Tape:... _ X [X] Y Y _ ...
- 動作: ヘッド右移動、状態
- ステップ 11: State:
q_start
, Head:X
. Rule:X
->X
, R,q_start
.- 動作: ヘッド右移動、状態
q_start
のまま。 - シミュレーター: State:
q_start
, Tape:... _ X X [Y] Y _ ...
- 動作: ヘッド右移動、状態
- ステップ 12: State:
q_start
, Head:Y
. Rule:Y
->Y
, R,q_check_all_y
.- 動作: ヘッド右移動、状態
q_check_all_y
。a
の処理が終わり、残りがY
だけか確認へ。 - シミュレーター: State:
q_check_all_y
, Tape:... _ X X Y [Y] _ ...
- 動作: ヘッド右移動、状態
- ステップ 13: State:
q_check_all_y
, Head:Y
. Rule:Y
->Y
, R,q_check_all_y
.- 動作: ヘッド右移動、状態
q_check_all_y
のまま。 - シミュレーター: State:
q_check_all_y
, Tape:... _ X X Y Y [_] ...
- 動作: ヘッド右移動、状態
- ステップ 14: State:
q_check_all_y
, Head:_
. Rule:_
->_
, R,q_accept
.- 動作: ヘッド右移動、状態
q_accept
。受理。 - シミュレーター: State:
q_accept
, Tape:... _ X X Y Y _ [_] ...
- 動作: ヘッド右移動、状態
このように、入力 aabb
は定義された遷移ルールに従って q_accept
状態に到達するため、受理されます。
非受理となる例: aab
での動作追跡
入力 aab
の場合、同様の手順で最初の2つの a
は X
に、最初の1つの b
は Y
に置換されます。テープが ... _ X X Y [_] ...
となった後、ヘッドは _
に、状態は q_check_all_y
に達します。
- ... ステップ 8 まで同様、テープ
... _ X X Y [b] _ ...
、状態q_find_b
- シミュレーター: State:
q_find_b
, Tape:... _ X X Y [b] _ ...
- シミュレーター: State:
- ステップ 9: State:
q_find_b
, Head:_
. Rule:_
->_
, R,q_reject
. (入力aab
ではステップ8でb
ではなく_
に到達)- 動作: ヘッド右移動、状態
q_reject
。非受理。 - シミュレーター: State:
q_reject
, Tape:... _ X X Y _ [_] ...
- 動作: ヘッド右移動、状態
このように、a
に対応する b
が見つからずにテープの終端に到達した場合など、正しくない形式の入力は q_reject
状態に遷移し、非受理となります。シミュレーターを用いることで、このような非受理となるケースの動作も詳細に確認できます。
シミュレーターと理論の対応
シミュレーターの画面上では、通常、以下の要素が表示されます。
- 状態遷移図: チューリングマシンの状態(ノード)と遷移ルール(エッジ)を視覚化したものです。本記事で解説した
q_start
,q_find_b
,q_find_x
,q_check_all_y
,q_accept
,q_reject
といった状態がノードとして、矢印が遷移ルールとして表示されます。各エッジには「読み取る記号 / 書き込む記号, ヘッドの移動方向」というラベルが付きます。 - テープ: 入力文字列が書かれたテープとその周辺の空白が表示されます。ヘッドの位置が強調表示されます。
- 現在の状態: マシンが現在どの状態にあるかが示されます。状態遷移図上の対応するノードがハイライトされるシミュレーターもあります。
- 制御部(ヘッド): 現在ヘッドが指しているテープ上の記号が表示されます。
理論的なチューリングマシンの定義における「状態」「アルファベット」「遷移関数」「テープ」「ヘッド」といった要素が、シミュレーターのこれらの表示要素と直接的に対応しています。シミュレーターの「ステップ実行」機能は、現在の状態とヘッド下の記号に基づき、遷移関数に従って次の状態、テープへの書き込み、ヘッドの移動を実行する過程を忠実に再現します。
例えば、ステップ実行時に状態が q_find_b
でヘッド下の記号が b
であった場合、シミュレーターは状態遷移図の中から q_find_b
ノードから出ていて、ラベルが b / Y, L
のエッジを探し出し、それに従ってテープ上の b
を Y
に書き換え、ヘッドを左に一つ移動させ、現在の状態をそのエッジが指す先の状態(q_find_x
)に変更します。この一連の動作がシミュレーター画面上で視覚的に確認できるのです。
まとめ
本記事では、チューリングマシンが { a^n b^n | n >= 0 }
形式の文字列を認識する仕組みについて解説しました。有限オートマトンでは困難なこのタスクが、チューリングマシンが持つテープという記憶媒体とヘッドの往復移動能力によって実現できることを示しました。
具体的なアルゴリズムとしては、a
と b
を対応付けながら順に処理済みマークに書き換え、最後に残りが全て処理済みマークと空白のみかを確認するという手順を踏みます。この過程における状態遷移、テープの内容変化、ヘッドの移動といったチューリングマシンの詳細な動作は、シミュレーターを用いることで視覚的に追跡し、理解を深めることが可能です。
計算機科学を学ぶ上で、理論上の計算モデルと具体的な動作の繋がりを理解することは非常に重要です。ぜひシミュレーターを活用し、様々な入力文字列を与えて動作を観察することで、チューリングマシンの能力と限界についての理解を一層深めてください。