オートマトン・形式言語の問題

難易度 2教科書の演習問題レベル大学数学オートマトン・形式言語

入力アルファベット $Σ = {0, 1}$ 、テープ記号の集合 $Γ = {0, 1, ⊔}$ （ $⊔$ は空白記号）をもつ 1 テープ決定性チューリング機械 $M$ を考える。状態の集合は ${q_{0}, q_{1}, q_{h}}$ で、初期状態は $q_{0}$ 、 $q_{h}$ は停止状態である（ $q_{h}$ に入った時点で $M$ は停止する）。遷移関数 $δ$ は次の表で与えられる。表の各欄の $(q^{'}, c, D)$ は「次の状態を $q^{'}$ にし、ヘッドの位置の記号を $c$ に書き換え、ヘッドを $D$ の向き（ $L$ は左、 $R$ は右）に 1 マス動かす」ことを表す。

状態 \\ 読んだ記号	$0$	$1$	$⊔$
$q_{0}$	$(q_{0}, 0, R)$	$(q_{0}, 1, R)$	$(q_{1}, ⊔, L)$
$q_{1}$	$(q_{h}, 1, L)$	$(q_{1}, 0, L)$	$(q_{h}, 1, L)$

テープは両側に無限に続き、はじめは入力文字列が連続するマスに書かれ、それ以外のマスはすべて $⊔$ である。ヘッドは最初、入力文字列の最も左の記号の上にある。遷移関数を 1 回適用することを 1 ステップと数える。

入力文字列 $w = 1101011$ を与えたとき、 $M$ が停止するまでのステップ数を求めよ。

この問題で使うもの

チューリング機械の動作の追跡（説明と入口の問題）

この問題を解けるようになるまで（2 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

状態 $q_{0}$ と状態 $q_{1}$ がそれぞれ何をしているかを、表から読み取ってみよう。

ヒント 2

$q_{0}$ は入力の右端の次の空白まで右へ進むだけで、 $q_{1}$ は右端から左へ $1$ を $0$ に書き換えていき、最初に $0$ か $⊔$ を読んだところで停止する。

ヒント 3

$q_{0}$ の間に、入力の $7$ 文字と空白 $1$ つを読むので $8$ ステップかかる。残りは、右端から続く $1$ の個数と最後の $1$ ステップを数えればよい。

答えと解説

答えを見る

11

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

$M$ の動作を状態ごとに追う。入力 $w = 1101011$ の長さは $7$ で、左から順にマス $1, 2, \dots, 7$ に書かれているとする。

状態 $q_{0}$ の動作

$q_{0}$ では $0$ も $1$ も書き換えずに右へ進み、 $⊔$ を読んだら $q_{1}$ に移って左へ 1 マス戻る。ヘッドはマス $1$ から始まり、マス $1$ 〜 $7$ の記号を読むのに $7$ ステップ、マス $8$ の $⊔$ を読むのに $1$ ステップかかる。ここまでで $7 + 1 = 8$ ステップで、ヘッドはマス $7$ にあり、状態は $q_{1}$ である。

状態 $q_{1}$ の動作

$q_{1}$ では $1$ を $0$ に書き換えながら左へ進み、 $0$ （または $⊔$ ）を読んだらそれを $1$ に書き換えて停止する。これは 2 進数に $1$ を加える繰り上がりの処理である。

第 $9$ ステップ: マス $7$ の $1$ を読み、 $0$ に書き換えて左へ。
第 $10$ ステップ: マス $6$ の $1$ を読み、 $0$ に書き換えて左へ。
第 $11$ ステップ: マス $5$ の $0$ を読み、 $1$ に書き換えて左へ動き、 $q_{h}$ に入って停止。

よって、停止するまでのステップ数は
$7 + 1 + 3 = 11$
である。なお、停止時のテープの内容は $1101100$ で、これは $w$ を 2 進数として読んだ値 $107$ に $1$ を加えた $108$ を表している。

答え: $11$

別解

テープの位置を左から 1, 2, ... と番号づけ、 $w = 1101011$ は位置 1〜7 に $1, 1, 0, 1, 0, 1, 1$ と書かれている。ヘッドは位置 1、状態は $q_{0}$ 。

ステップ 1〜7: $q_{0}$ は $0, 1$ を読むと書き換えずに右へ進む。位置 1〜7 を順に読み、7 ステップでヘッドは位置 8（ $⊔$ ）に来る。
ステップ 8: $q_{0}$ で $⊔$ を読む。 $(q_{1}, ⊔, L)$ により状態 $q_{1}$ 、位置 7 へ。
ステップ 9: $q_{1}$ で位置 7 の $1$ を読む。 $(q_{1}, 0, L)$ により $0$ に書き換え、位置 6 へ。
ステップ 10: $q_{1}$ で位置 6 の $1$ を読む。 $(q_{1}, 0, L)$ により $0$ に書き換え、位置 5 へ。
ステップ 11: $q_{1}$ で位置 5 の $0$ を読む。 $(q_{h}, 1, L)$ により $1$ に書き換え、停止状態 $q_{h}$ に入り停止。

最終テープは $1101100$ で、入力 $1101011$ に 1 を加えた 2 進数（ $107 + 1 = 108 = 110110 0_{2}$ 、ヘッドは位置 4 の左側から見て下位ビットが右）と一致し、動作（2 進数のインクリメント）と整合する。合計のステップ数は $7 + 1 + 3 = 11$ 。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる

関連する問題

状態	$1$	$+$	$⊔$
$q_{0}$	$(q_{0}, 1, R)$	$(q_{1}, 1, R)$	—
$q_{1}$	$(q_{1}, 1, R)$	—	$(q_{2}, ⊔, L)$
$q_{2}$	$(h, ⊔, L)$	—	—

難易度 3（期末試験の応用レベル）

次の 1 テープ決定性チューリング機械 $M$ を考える。

状態の集合: ${q_{0}, q_{1}, q_{2}, q_{3}, q_{acc}, q_{rej}}$ 。初期状態は $q_{0}$ 、受理状態は $q_{acc}$ 、拒否状態は $q_{rej}$
入力アルファベット: ${a, b}$ 、テープアルファベット: ${a, b, X, Y, ⊔}$ （ $⊔$ は空白記号）
遷移関数 $δ$ は次の表のとおり。表の「 $(p, c, D)$ 」は「状態を $p$ に変え、いま読んでいるマスに $c$ を書き、ヘッドを $D$ の向き（ $R$ は右、 $L$ は左）に 1 マス動かす」ことを表す。表にない（状態, 記号）の組では、 $M$ は $q_{rej}$ に移って停止する。

状態	読む記号	遷移
$q_{0}$	$a$	$(q_{1}, X, R)$
$q_{0}$	$Y$	$(q_{3}, Y, R)$
$q_{1}$	$a$	$(q_{1}, a, R)$
$q_{1}$	$Y$	$(q_{1}, Y, R)$
$q_{1}$	$b$	$(q_{2}, Y, L)$
$q_{2}$	$a$	$(q_{2}, a, L)$
$q_{2}$	$Y$	$(q_{2}, Y, L)$
$q_{2}$	$X$	$(q_{0}, X, R)$
$q_{3}$	$Y$	$(q_{3}, Y, R)$
$q_{3}$	$⊔$	$(q_{acc}, ⊔, R)$

テープは右に無限に続き、はじめは入力文字列が左端のマスから書かれ、残りのマスはすべて $⊔$ である。ヘッドははじめ左端のマス（入力の 1 文字目）にあり、状態は $q_{0}$ である。 $M$ は $q_{acc}$ または $q_{rej}$ に入った時点で停止する。

入力 $aaabbb$ に対して $M$ を動かしたとき、 $M$ が停止するまでに適用される遷移の回数（停止状態に入る遷移も 1 回と数える）を求めよ。

難易度 4（大学院入試の標準レベル）
両側に無限に続くテープを 1 本もつ決定性チューリング機械 $M$ を考える。
- 状態の集合: ${q_{0}, q_{1}, q_{2}, q_{3}, h}$ 。初期状態は $q_{0}$ 、停止状態は $h$ （ $h$ からの遷移はなく、 $h$ に入った時点で $M$ は停止する）
- 入力アルファベット: ${1}$ 、テープ記号の集合: ${1, ⊔}$ （ $⊔$ は空白記号）
- 遷移関数 $δ$ は次の表で与えられる。表の「(書く記号, ヘッドの移動, 次の状態)」で、 $R$ は右へ 1 マス、 $L$ は左へ 1 マス動くことを表す。
状態読んだ記号 $1$ 読んだ記号 $⊔$
$q_{0}$ $(⊔, R, q_{1})$ $(⊔, R, h)$
$q_{1}$ $(1, R, q_{1})$ $(⊔, L, q_{2})$
$q_{2}$ $(⊔, L, q_{3})$ $(⊔, R, h)$
$q_{3}$ $(1, L, q_{3})$ $(⊔, R, q_{0})$
$n$ を 0 以上の整数とする。はじめ、テープには連続する $n$ マスに $1$ が書かれ（入力 $1^{n}$ ）、それ以外のマスはすべて $⊔$ である。ヘッドは入力の左端のマス（ $n = 0$ のときは任意の 1 マス）にあり、状態は $q_{0}$ である。
遷移関数を 1 回適用することを 1 ステップと数える（ $h$ に入る遷移も 1 ステップに数える）。入力 $1^{n}$ に対して $M$ が停止するまでのステップ数を $n$ の式で求めよ。