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

この記事では、言語 L = {aⁱb^jc^k | i > j > k、k ≥ 1} を認識するチューリングマシンの構築方法を解説します。この言語は、記号 a、b、c のみから構成される文字列のうち、「a の個数が b の個数より多く、さらに b の個数が c の個数より多い」という条件を満たすものの集合を表します。

言語の定義と具体例

例えば、w = aaaaaabbbbccc(a が 6 個、b が 4 個、c が 3 個)という入力文字列は、6 > 4 > 3 ≥ 1 という条件を満たしているため、このチューリングマシンによって受理されます。

一方で、a と b の個数が等しい文字列や、b の個数が c の個数以下である文字列などは条件を満たさないため、拒否されます。

構築のアプローチ

この問題を解くためには、テープ上の記号をマークしながら段階的に個数を比較していく手法を用います。具体的な手順は以下の通りです。

1. まず、a と b を 1 対ずつ対応付けてマークし(例：a を X に、b を Y に書き換え)、両者の個数を比較します。
2. 次に、残った b と c を同様にマークしながら比較します。
3. c の個数が b の個数以上である場合(|C| ≥ |B|)、その文字列は受理されません。
4. b の個数が a の個数以上である場合(|B| ≥ |A|)、その文字列も受理されません。
5. 上記のいずれにも該当しない場合、すなわち i > j > k ≥ 1 という条件が成立していれば、その文字列は受理されます。

状態遷移図

以下の状態遷移図は、上述のロジックを実装したチューリングマシンの動作を表しています。各状態間の遷移を追うことで、マーキングによる比較処理と最終的な受理判定の流れを確認できます。