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

難易度 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$ の式で求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

左端の $1$ を消して右端まで行き、右端の $1$ を消して左端まで戻る、という「1 周」を単位に考える。1 周ごとに $1$ の個数がどう変わるかを調べる。

ヒント 2

1 周の始めに $1$ が $k$ 個（ $k \geq 2$ ）あるとき、その周のステップ数を $k$ で表すと $2 k + 1$ になる。最後に残る $1$ の個数が $0$ 個か $1$ 個かで、終わり方とステップ数が違う。

ヒント 3

$n$ が偶数 $2 m$ なら周の長さは $k = 2 m, 2 m - 2, \dots, 2$ で最後に $1$ ステップ、 $n$ が奇数 $2 m + 1$ なら $k = 2 m + 1, \dots, 3$ で最後に $3$ ステップかかる。それぞれ和を計算して $n$ で書き直す。

答えと解説

答えを見る

\frac{( n + 1 ) ( n + 2 )}{2}

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

解説を読む

テープのマスに左から番号を付け、入力の $1$ はマス $1, 2, \dots, n$ にあるとする。

1 周の動作. ある時点で、状態 $q_{0}$ 、ヘッドがマス $l$ にあり、マス $l$ からマス $r$ までの $k = r - l + 1$ マス（ $k \geq 0$ ）に $1$ が連続して並び、それ以外はすべて $⊔$ であるとする。この状況からの動作を調べる。

(i) $k = 0$ のとき: $q_{0}$ が $⊔$ を読み、 $h$ に入って停止する。1 ステップ。

(ii) $k \geq 1$ のとき:
- $q_{0}$ がマス $l$ の $1$ を $⊔$ に書き換え、右へ動いて $q_{1}$ になる: $1$ ステップ。
- $q_{1}$ はマス $l + 1, \dots, r$ の $1$ の上を右へ進む: $k - 1$ ステップ。マス $r + 1$ で $⊔$ を読み、左へ動いて $q_{2}$ になる: $1$ ステップ。このときヘッドはマス $r$ にある。

(ii-a) $k = 1$ のとき: $r = l$ なのでマス $r$ はすでに $⊔$ である。 $q_{2}$ が $⊔$ を読んで停止する: $1$ ステップ。合計 $1 + 0 + 1 + 1 = 3$ ステップで停止する。

(ii-b) $k \geq 2$ のとき:
- $q_{2}$ がマス $r$ の $1$ を $⊔$ に書き換え、左へ動いて $q_{3}$ になる: $1$ ステップ。
- $q_{3}$ はマス $r - 1, \dots, l + 1$ の $1$ の上を左へ進む: $k - 2$ ステップ。マス $l$ で $⊔$ を読み、右へ動いて $q_{0}$ になる: $1$ ステップ。

この 1 周のステップ数は
$1 + (k - 1) + 1 + 1 + (k - 2) + 1 = 2 k + 1$
で、終わったときは状態 $q_{0}$ 、ヘッドはマス $l + 1$ にあり、 $1$ の列はマス $l + 1$ からマス $r - 1$ までの $k - 2$ マスになっている。つまり同じ形の状況に、 $k$ が $2$ 減って戻る。

合計. 長さを $T (k)$ で表すと $T (0) = 1, T (1) = 3, T (k) = T (k - 2) + 2 k + 1 (k \geq 2)$ である。

$n = 2 m$ （ $m \geq 0$ ）のとき:
$T (2 m) = j = 1 \sum m (4 j + 1) + 1 = 4 \cdot \frac{m ( m + 1 )}{2} + m + 1 = 2 m^{2} + 3 m + 1 = (m + 1) (2 m + 1) .$
$m = \frac{n}{2}$ を代入すると $(\frac{n}{2} + 1) (n + 1) = \frac{( n + 1 ) ( n + 2 )}{2}$ 。

$n = 2 m + 1$ （ $m \geq 0$ ）のとき: 周の長さは $k = 2 m + 1, 2 m - 1, \dots, 3$ で、そのあと $k = 1$ の 3 ステップが続く。
$T (2 m + 1) = j = 1 \sum m (2 (2 j + 1) + 1) + 3 = j = 1 \sum m (4 j + 3) + 3 = 2 m (m + 1) + 3 m + 3 = 2 m^{2} + 5 m + 3 = (m + 1) (2 m + 3) .$
$m = \frac{n - 1}{2}$ を代入すると $\frac{n + 1}{2} (n + 2) = \frac{( n + 1 ) ( n + 2 )}{2}$ 。

どちらの場合も同じ式になるので、求めるステップ数は
$\frac{( n + 1 ) ( n + 2 )}{2}$
である（確認: $n = 0, 1, 2$ で $1, 3, 6$ ステップ。たとえば $n = 2$ では 1 周 $5$ ステップのあと $k = 0$ で $1$ ステップ）。

別解

テープの 1 が $m$ 個連続し、ヘッドがその左端にあって状態が $q_{0}$ の「局面」から、停止または次の局面に至るまでを調べる。

(i) $m = 0$ : $q_{0}$ が $⊔$ を読み $h$ へ。1 ステップ。

(ii) $m = 1$ : $q_{0}$ が $1$ を消して右へ（1）。 $q_{1}$ が $⊔$ を読み左へ $q_{2}$ （1）。 $q_{2}$ が（消した） $⊔$ を読み右へ $h$ （1）。計 3 ステップ。

(iii) $m \geq 2$ :
- $q_{0}$ が左端の $1$ を消して右へ: 1 ステップ。
- $q_{1}$ が残り $m - 1$ 個の 1 を右へ読み飛ばす: $m - 1$ ステップ。
- $q_{1}$ が $⊔$ を読み、左へ $q_{2}$ : 1 ステップ。
- $q_{2}$ が右端の $1$ を消して左へ $q_{3}$ : 1 ステップ。
- $q_{3}$ が残り $m - 2$ 個の 1 を左へ読み飛ばす: $m - 2$ ステップ。
- $q_{3}$ が（左端を消した跡の） $⊔$ を読み右へ $q_{0}$ : 1 ステップ。

計 $1 + (m - 1) + 1 + 1 + (m - 2) + 1 = 2 m + 1$ ステップで、1 が $m - 2$ 個に減り、ヘッドは新しい左端で状態 $q_{0}$ に戻る（ $m = 2$ のときは 1 が 0 個で、ヘッドは空白の上）。

よって総ステップ数 $T (n)$ は:

$n$ が偶数のとき、 $m = n, n - 2, \dots, 2$ の各回で $2 m + 1$ 、最後に $m = 0$ の 1 ステップ。 $m = 2 k$ $(k = 1, \dots, n /2)$ として
$T (n) = k = 1 \sum n /2 (4 k + 1) + 1 = \frac{n ( n + 2 )}{2} + \frac{n}{2} + 1 = \frac{n ^{2} + 3 n + 2}{2} .$

$n$ が奇数のとき、 $m = n, \dots, 3$ の各回で $2 m + 1$ 、最後に $m = 1$ の 3 ステップ。 $m = 2 k + 1$ $(k = 1, \dots, K = \frac{n - 1}{2})$ として
$T (n) = k = 1 \sum K (4 k + 3) + 3 = 2 K^{2} + 5 K + 3 = \frac{n ^{2} + 3 n + 2}{2} .$

どちらも $T (n) = \frac{( n + 1 ) ( n + 2 )}{2}$ 。

検算: $n = 0$ で 1、 $n = 1$ で 3、 $n = 2$ で $5 + 1 = 6$ 、 $n = 3$ で $7 + 3 = 10$ 。式の値 $1, 3, 6, 10$ と一致する。

この問題の確認

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

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

確認の方法について

間違いを報告する

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

関連する問題

難易度 2（教科書の演習問題レベル）
両側に無限に続くテープを 1 本もつ決定性チューリング機械 $M$ を考える。
- 状態の集合は ${q_{0}, q_{1}, q_{2}, h}$ である。初期状態は $q_{0}$ 、停止状態は $h$ である。 $h$ からの遷移はなく、 $h$ に入った時点で $M$ は停止する。
- 入力アルファベットは ${0, 1}$ 、テープ記号の集合は ${0, 1, ⊔}$ である（ $⊔$ は空白記号）。
- 遷移関数 $δ$ は次の表で与えられる。表の各欄の $(p, c, D)$ は「状態 $p$ に移り、ヘッドの位置に記号 $c$ を書き込み、ヘッドを向き $D$ に 1 マス動かす」ことを表す。 $L$ は左、 $R$ は右である。
状態 \ 読んだ記号 $0$ $1$ $⊔$
$q_{0}$ $(q_{0}, 0, R)$ $(q_{0}, 1, R)$ $(q_{1}, ⊔, L)$
$q_{1}$ $(q_{2}, 1, L)$ $(q_{1}, 0, L)$ $(q_{2}, 1, L)$
$q_{2}$ $(q_{2}, 0, L)$ $(q_{2}, 1, L)$ $(h, ⊔, R)$
最初、テープには入力文字列 $w = 10110111$ が左から順に 1 マスに 1 文字ずつ書かれている。それ以外のマスはすべて $⊔$ である。ヘッドは $w$ の左端の文字の上にあり、状態は $q_{0}$ である。
遷移関数を 1 回適用することを 1 ステップと数える。 $h$ に移る遷移も 1 ステップに含める。 $M$ が停止するまでのステップ数を求めよ。

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

難易度 4（大学院入試の標準レベル）

入力アルファベット $Σ = {a, b}$ 、テープ記号の集合 $Γ = {a, b, X, Y, ⊔}$ （ $⊔$ は空白記号）をもつ 1 テープ決定性チューリング機械 $M$ を考える。

状態の集合は ${q_{0}, q_{1}, q_{2}, q_{3}, q_{acc}, q_{rej}}$ であり、初期状態は $q_{0}$ 、受理状態は $q_{acc}$ 、拒否状態は $q_{rej}$ である。 $M$ は $q_{acc}$ または $q_{rej}$ に入った時点で停止する。
テープのマスには左から順に番号 $1, 2, 3, \dots$ が付いており、入力 $w$ はマス $1$ から $∣ w ∣$ に 1 文字ずつ書かれ、ほかのマスはすべて $⊔$ である。最初、ヘッドはマス $1$ にある。
遷移関数 $δ$ は次の表で与えられる。表の $(p, c, D)$ は「状態 $p$ に移り、いまのマスに記号 $c$ を書き、ヘッドを $D$ の向きに 1 マス動かす（ $R$ は右、 $L$ は左）」ことを表す。

状態	$a$	$b$	$X$	$Y$	$⊔$
$q_{0}$	$(q_{1}, X, R)$	$(q_{rej}, b, R)$	$(q_{rej}, X, R)$	$(q_{3}, Y, R)$	$(q_{acc}, ⊔, R)$
$q_{1}$	$(q_{1}, a, R)$	$(q_{2}, Y, L)$	$(q_{rej}, X, R)$	$(q_{1}, Y, R)$	$(q_{rej}, ⊔, R)$
$q_{2}$	$(q_{2}, a, L)$	$(q_{rej}, b, R)$	$(q_{0}, X, R)$	$(q_{2}, Y, L)$	$(q_{rej}, ⊔, R)$
$q_{3}$	$(q_{rej}, a, R)$	$(q_{rej}, b, R)$	$(q_{rej}, X, R)$	$(q_{3}, Y, R)$	$(q_{acc}, ⊔, R)$

遷移関数を 1 回適用することを 1 ステップと数える（ $q_{acc}$ や $q_{rej}$ に移る遷移も 1 ステップと数える）。

$m, n$ を $m > n \geq 1$ を満たす整数とする。入力 $w = a^{m} b^{n}$ （ $a$ を $m$ 個並べた後に $b$ を $n$ 個並べた文字列）に対して $M$ を動かしたとき、 $M$ が停止するまでのステップ数を $m, n$ の式で求めよ。

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

状態 \\ 読んだ記号	$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)$

難易度 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 回と数える）を求めよ。