L = {AⁱBʲCᵏ | i < j < k、i ≥ 1} を認識するチューリングマシンの構築方法

ここでは、言語 L = {AⁱBʲCᵏ | i < j < k、i ≥ 1} を認識するチューリングマシンの構築方法を解説します。この言語は A・B・C の 3 種類の記号のみで構成される文字列を扱い、B の個数が A の個数より厳密に多く、さらに C の個数が B の個数より厳密に多いことが条件となります。w は入力文字列を表します。たとえば w = AABBBBCCCCC の場合、A が 2 個・B が 4 個・C が 5 個であり、2 < 4 < 5 という条件を満たすため、このチューリングマシンは文字列を受け入れます。

解法のアプローチ

この問題を解く基本的な考え方は、記号を 1 組ずつペアとして比較していくことです。まず A と B を 1 つのまとまりとして対応付け、A をすべて処理し終えた後も B が残っていることを確認します。これにより「B の数 > A の数」という条件を検証できます。続いて、残った B と C を同様に対応付けて比較し、B をすべて処理した後も C が残っていれば「C の数 > B の数」も満たされます。これらの条件がすべて成り立った場合にのみ文字列は受け入れられ、それ以外の場合は拒否されます。

処理の手順

1. 先頭の A を 1 つ読み込んで印を付け、対応する B を 1 つ探して印を付けます。
2. A がすべて印付けされるまでこの操作を繰り返します。途中で対応する B が見つからなければ、文字列を拒否します。
3. 次に、まだ印の付いていない残りの B と C を 1 組ずつ対応付けます。B に対して C が足りなければ拒否します。
4. すべての比較が成功し、最後に C が少なくとも 1 つ残っていれば、文字列を受け入れます。

状態遷移図

以下の状態遷移図は、上記のアプローチに基づいてこの言語を認識するチューリングマシンの状態と遷移を示したものです。