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

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

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

この機械は「 $a$ を $X$ に、対応する $b$ を $Y$ に書き換える往復」をくり返す。1 往復ごとにテープの様子とヘッドの位置を書き出してみよう。

ヒント 2

1 往復は「 $q_{0}$ で 1 回」「 $q_{1}$ で右へ進み $b$ を $Y$ にするまで」「 $q_{2}$ で左へ戻り $X$ を読むまで」に分けて数えるとよい。

ヒント 3

1 往復目は $q_{0}$ で 1 回、 $q_{1}$ で 3 回、 $q_{2}$ で 3 回の計 7 回になる。2 往復目、3 往復目も同様に数え、最後に $q_{3}$ で $Y$ を通過して空白に達するまでを加えよう。

答えと解説

答えを見る

25

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

解説を読む

マスを左から $1, 2, 3, \dots$ と番号付けする。入力は $1 \sim 3$ 番目が $a$ 、 $4 \sim 6$ 番目が $b$ 、7 番目以降が $⊔$ である。

$M$ の動作は「 $q_{0}$ で左端の未処理の $a$ を $X$ にする → $q_{1}$ で右へ進み最初の $b$ を $Y$ にする → $q_{2}$ で左へ戻り $X$ を見つけたら 1 マス右へ」という 1 往復をくり返す。

1 往復目（ヘッドは 1 番目）
- $q_{0}$ : 1 番目の $a$ を $X$ に、右へ（1 回）
- $q_{1}$ : 2, 3 番目の $a$ を通過（2 回）、4 番目の $b$ を $Y$ にして左へ（1 回）
- $q_{2}$ : 3, 2 番目の $a$ を通過（2 回）、1 番目の $X$ を読んで右へ、 $q_{0}$ に（1 回）

計 $1 + 3 + 3 = 7$ 回。テープは $X aaY bb$ 、ヘッドは 2 番目。

2 往復目
- $q_{0}$ : 2 番目の $a$ を $X$ に（1 回）
- $q_{1}$ : 3 番目の $a$ 、4 番目の $Y$ を通過（2 回）、5 番目の $b$ を $Y$ に（1 回）
- $q_{2}$ : 4 番目の $Y$ 、3 番目の $a$ を通過（2 回）、2 番目の $X$ で右へ（1 回）

計 $7$ 回。テープは $X X aY Y b$ 、ヘッドは 3 番目。

3 往復目
- $q_{0}$ : 3 番目の $a$ を $X$ に（1 回）
- $q_{1}$ : 4, 5 番目の $Y$ を通過（2 回）、6 番目の $b$ を $Y$ に（1 回）
- $q_{2}$ : 5, 4 番目の $Y$ を通過（2 回）、3 番目の $X$ で右へ（1 回）

計 $7$ 回。テープは $X X X Y Y Y$ 、ヘッドは 4 番目、状態は $q_{0}$ 。

最後の確認
- $q_{0}$ : 4 番目の $Y$ を読み $q_{3}$ へ（1 回）
- $q_{3}$ : 5, 6 番目の $Y$ を通過（2 回）
- $q_{3}$ : 7 番目の $⊔$ を読み $q_{acc}$ へ（1 回）

計 $4$ 回で受理して停止する。

したがって遷移の回数は
$7 + 7 + 7 + 4 = 25$

（一般に入力 $a^{n} b^{n}$ では 1 往復が $1 + n + n = 2 n + 1$ 回、最後が $n + 1$ 回なので、合計 $n (2 n + 1) + n + 1 = 2 n^{2} + 2 n + 1$ 回となり、 $n = 3$ で $25$ と一致する。）

別解

テープの位置を左端から 0,1,2,... とする。初期のテープは $aaabbb ⊔$ 、ヘッドは位置 0、状態は $q_{0}$ 。

1 周目: $q_{0}$ が $a$ （位置 0）を $X$ に変えて右へ（1 回）。 $q_{1}$ が位置 1 の $a$ 、位置 2 の $a$ を読み右へ（2 回）、位置 3 の $b$ を $Y$ に変えて $q_{2}$ で左へ（1 回）。 $q_{2}$ が位置 2、1 の $a$ を読み左へ（2 回）、位置 0 の $X$ で $q_{0}$ に戻り右へ（1 回）。合計 $1 + 3 + 3 = 7$ 回。テープは $X aaY bb$ 、ヘッドは位置 1、状態は $q_{0}$ 。

2 周目: 同様に $q_{0}$ で位置 1 の $a$ を $X$ に（1 回）、 $q_{1}$ が位置 2 の $a$ 、位置 3 の $Y$ を右へ越え、位置 4 の $b$ を $Y$ に（3 回）、 $q_{2}$ が位置 3 の $Y$ 、位置 2 の $a$ を左へ越え、位置 1 の $X$ で $q_{0}$ に（3 回）。合計 7 回。テープは $X X aY Y b$ 、ヘッドは位置 2。

3 周目: $q_{0}$ で位置 2 の $a$ を $X$ に（1 回）、 $q_{1}$ が位置 3、4 の $Y$ を越え、位置 5 の $b$ を $Y$ に（3 回）、 $q_{2}$ が位置 4、3 の $Y$ を越え、位置 2 の $X$ で $q_{0}$ に（3 回）。合計 7 回。テープは $X X X Y Y Y ⊔$ 、ヘッドは位置 3、状態は $q_{0}$ 。

最後: $q_{0}$ が位置 3 の $Y$ を読んで $q_{3}$ に移り右へ（1 回）。 $q_{3}$ が位置 4、5 の $Y$ を読み右へ（2 回）、位置 6 の $⊔$ で $q_{acc}$ に移る（1 回）。合計 4 回。

総回数: $7 \times 3 + 4 = 25$ 。入力は受理される。

答え: 25

この問題の確認

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

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

確認の方法について

間違いを報告する

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

関連する問題

難易度 1（教科書の例題レベル）
1 テープ決定性チューリング機械 $M$ を考える。
- 入力アルファベット: $Σ = {1, +}$
- テープ記号の集合: $Γ = {1, +, ⊔}$ （ $⊔$ は空白記号）
- 状態の集合: ${q_{0}, q_{1}, q_{2}, h}$ 。初期状態は $q_{0}$ 、停止状態は $h$ である（ $h$ からの遷移はない）。
- テープは右に無限に続き、はじめは左端のマスから順に入力文字列が書かれ、残りのマスはすべて $⊔$ である。ヘッドは左端のマス（入力の 1 文字目）にあり、状態は $q_{0}$ である。
遷移関数 $δ$ は次の表で与えられる。表の $(p, c, D)$ は「状態 $p$ に移り、いま読んでいるマスに記号 $c$ を書き、ヘッドを $D$ の向き（ $R$ は右、 $L$ は左）に 1 マス動かす」ことを表す。「—」の組では遷移は定義されていない。
状態 $1$ $+$ $⊔$
$q_{0}$ $(q_{0}, 1, R)$ $(q_{1}, 1, R)$ —
$q_{1}$ $(q_{1}, 1, R)$ — $(q_{2}, ⊔, L)$
$q_{2}$ $(h, ⊔, L)$ — —
遷移を 1 回適用することを 1 ステップと数える。入力文字列 $111 + 11$ を与えて $M$ を動かしたとき、状態が $h$ になるまでに何ステップかかるか求めよ。

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

難易度 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}$	$(q_{h}, 1, L)$	$(q_{1}, 0, L)$	$(q_{h}, 1, L)$

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