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

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

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

まず短い入力（たとえば $aab$ ）で $M$ を 1 ステップずつ追跡し、各状態がどんな役割をしているか（どの記号を書き換え、どちらへ進むか）をつかもう。

ヒント 2

$q_{0} \to q_{1} \to q_{2} \to q_{0}$ の 1 回の往復で、 $a$ が 1 つ $X$ に、 $b$ が 1 つ $Y$ に変わる。第 $i$ 往復の開始時のテープの様子を書き、右へ進むステップ数と左へ戻るステップ数を $m$ で表してみよう。

ヒント 3

1 往復は $i$ によらず $2 m + 1$ ステップである。 $n$ 往復で $b$ がなくなった後、 $q_{0}$ はまだ残っている $a$ を読む。そこから $q_{1}$ が右端の $⊔$ に着くまでのステップ数を数えよう。

答えと解説

答えを見る

2 mn + m + n + 1

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

解説を読む

入力 $a^{m} b^{n}$ では、マス $1$ 〜 $m$ に $a$ 、マス $m + 1$ 〜 $m + n$ に $b$ があり、マス $m + n + 1$ 以降は $⊔$ である。

$M$ は、状態 $q_{0}$ で左端の未処理の $a$ を $X$ に書き換え、 $q_{1}$ で右へ進んで最初の $b$ を $Y$ に書き換え、 $q_{2}$ で左へ戻って $X$ の右隣に戻る、という往復を繰り返す。

第 $i$ 往復（ $1 \leq i \leq n$ ）

第 $i$ 往復の開始時、状態は $q_{0}$ 、ヘッドはマス $i$ にあり、マス $1$ 〜 $i - 1$ は $X$ 、マス $i$ 〜 $m$ は $a$ 、マス $m + 1$ 〜 $m + i - 1$ は $Y$ 、マス $m + i$ 〜 $m + n$ は $b$ である（ $i = 1$ のときも同様）。

$q_{0}$ がマス $i$ の $a$ を $X$ にして右へ: $1$ ステップ。
$q_{1}$ はマス $i + 1$ 〜 $m + i - 1$ （ $a$ または $Y$ ）を右へ進む: $(m + i - 1) - (i + 1) + 1 = m - 1$ ステップ。
$q_{1}$ がマス $m + i$ の $b$ を $Y$ にして左へ、 $q_{2}$ になる: $1$ ステップ。
$q_{2}$ はマス $m + i - 1$ 〜 $i + 1$ （ $a$ または $Y$ ）を左へ進む: $m - 1$ ステップ。
$q_{2}$ がマス $i$ の $X$ を読んで右へ、 $q_{0}$ になる: $1$ ステップ。

よって 1 往復は $1 + (m - 1) + 1 + (m - 1) + 1 = 2 m + 1$ ステップで、終了後は状態 $q_{0}$ 、ヘッドはマス $i + 1$ にあり、上の形が $i$ を $i + 1$ にして保たれる。 $n$ 往復で合計
$n (2 m + 1)$
ステップである。

最後の部分

$n$ 往復の後、状態は $q_{0}$ 、ヘッドはマス $n + 1$ にあり、マス $1$ 〜 $n$ は $X$ 、マス $n + 1$ 〜 $m$ は $a$ 、マス $m + 1$ 〜 $m + n$ は $Y$ で、 $b$ は残っていない。 $m > n$ よりマス $n + 1$ は $a$ である。

$q_{0}$ がマス $n + 1$ の $a$ を $X$ にして右へ: $1$ ステップ。
$q_{1}$ はマス $n + 2$ 〜 $m + n$ （ $a$ または $Y$ ）を右へ進む: $(m + n) - (n + 2) + 1 = m - 1$ ステップ。
$q_{1}$ がマス $m + n + 1$ の $⊔$ を読み、 $q_{rej}$ に移って停止する: $1$ ステップ。

この部分は $1 + (m - 1) + 1 = m + 1$ ステップである。

合計
$n (2 m + 1) + (m + 1) = 2 mn + m + n + 1$

（確認: $m = 2, n = 1$ の入力 $aab$ では、実際に追跡すると $8$ ステップで停止し、 $2 \cdot 2 \cdot 1 + 2 + 1 + 1 = 8$ と一致する。）

別解

入力 $a^{m} b^{n}$ では、マス $1, \dots, m$ が $a$ 、マス $m + 1, \dots, m + n$ が $b$ である。

【第 $k$ 周回（ $k = 1, \dots, n$ ）】周回の始めは、マス $1, \dots, k - 1$ が $X$ 、マス $m + 1, \dots, m + k - 1$ が $Y$ で、ヘッドはマス $k$ （ $a$ ）にあり状態は $q_{0}$ である（ $k = 1$ のときは初期状態）。
- $q_{0}$ が $a$ を $X$ に書き換えて右へ（ $q_{1}$ ）: 1 ステップ。ヘッドはマス $k + 1$ 。
- $q_{1}$ が $a$ と $Y$ を読み飛ばして右へ進み、最初の $b$ （マス $m + k$ ）に着くまで: マス $k + 1, \dots, m + k - 1$ を読むので $m - 1$ ステップ。
- $q_{1}$ が $b$ を $Y$ に書き換えて左へ（ $q_{2}$ ）: 1 ステップ。ヘッドはマス $m + k - 1$ 。
- $q_{2}$ が $a$ と $Y$ を読み飛ばして左へ進み、 $X$ （マス $k$ ）に着くまで: マス $m + k - 1, \dots, k + 1$ を読むので $m - 1$ ステップ。
- $q_{2}$ が $X$ を読み、 $q_{0}$ に移って右へ: 1 ステップ。ヘッドはマス $k + 1$ 。

合計 $1 + (m - 1) + 1 + (m - 1) + 1 = 2 m + 1$ ステップ。これが $n$ 回続く（ $m > n$ なので毎回 $a$ が残っている）。

【第 $n + 1$ 周回】 $n$ 周回後、ヘッドはマス $n + 1$ で状態は $q_{0}$ 。 $m > n$ より、マス $n + 1, \dots, m$ は $a$ （少なくとも 1 個）、マス $m + 1, \dots, m + n$ は $Y$ 、マス $m + n + 1$ 以降は空白である。
- $q_{0}$ が $a$ を $X$ に書き換えて右へ（ $q_{1}$ ）: 1 ステップ。ヘッドはマス $n + 2$ 。
- $q_{1}$ が $a$ と $Y$ を読み飛ばして右へ進む: マス $n + 2, \dots, m + n$ を読むので $m - 1$ ステップ。
- マス $m + n + 1$ の空白を $q_{1}$ が読み、 $q_{rej}$ に移る: 1 ステップ。

合計 $m + 1$ ステップで拒否して停止する。

【総ステップ数】
$n (2 m + 1) + (m + 1) = 2 mn + m + n + 1$ 。

【検算】 $m = 2, n = 1$ （ $w = aab$ ）: $q_{0}$ (マス1, $a$ )→ $q_{1}$ マス2 [1]、 $a$ を読み右へマス3 [2]、 $b$ を $Y$ にして左へマス2 [3]、 $q_{2}$ が $a$ を読み左へマス1 [4]、 $X$ を読み $q_{0}$ で右へマス2 [5]。 $q_{0}$ が $a$ を $X$ にして右へマス3 [6]、 $q_{1}$ が $Y$ を読み右へマス4 [7]、空白を読み $q_{rej}$ へ [8]。計 8 ステップ。式: $2 \cdot 2 \cdot 1 + 2 + 1 + 1 = 8$ で一致。

この問題の確認

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

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

確認の方法について

間違いを報告する

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

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

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

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

状態	読む記号 $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)$