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

難易度 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$ になるまでに何ステップかかるか求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

チューリング機械の動作の追跡を使う。状態・テープの内容・ヘッドの位置（様相）を、遷移表に従って 1 ステップずつ書き出していく。

ヒント 2

各ステップでは「いまの状態」と「ヘッドが読んでいる記号」の組で表を引き、書く記号・ヘッドの向き・次の状態を決める。 $q_{0}$ は $1$ を読み飛ばして右へ進み、 $+$ を $1$ に書き換えて $q_{1}$ に移る。

ヒント 3

最初の 3 ステップで $111$ を読み飛ばし、4 ステップ目で $+$ を $1$ に書き換えて $q_{1}$ になる。その後 $q_{1}$ が右端の空白に着くまで右へ進み、空白で左に戻って $q_{2}$ になる。そこから $h$ に入るまでを数えよう。

答えと解説

答えを見る

8

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

解説を読む

様相（状態・テープの内容・ヘッドの位置）を 1 ステップずつ追跡する。様相を $u q v$ と書き、「テープの内容は $uv$ 、状態は $q$ 、ヘッドは $v$ の 1 文字目を読んでいる」ことを表す。

はじめ（0 ステップ）: $q_{0} 111 + 11$

1. 状態 $q_{0}$ で $1$ を読む → $(q_{0}, 1, R)$ 。 $1$ をそのまま残して右へ。様相 $1 q_{0} 11 + 11$
2. $q_{0}$ で $1$ → $(q_{0}, 1, R)$ 。様相 $11 q_{0} 1 + 11$
3. $q_{0}$ で $1$ → $(q_{0}, 1, R)$ 。様相 $111 q_{0} + 11$
4. $q_{0}$ で $+$ → $(q_{1}, 1, R)$ 。 $+$ を $1$ に書き換えて右へ、状態 $q_{1}$ 。様相 $1111 q_{1} 11$
5. $q_{1}$ で $1$ → $(q_{1}, 1, R)$ 。様相 $11111 q_{1} 1$
6. $q_{1}$ で $1$ → $(q_{1}, 1, R)$ 。様相 $111111 q_{1} ⊔$
7. $q_{1}$ で $⊔$ → $(q_{2}, ⊔, L)$ 。左へ戻り状態 $q_{2}$ 。様相 $11111 q_{2} 1$
8. $q_{2}$ で $1$ → $(h, ⊔, L)$ 。右端の $1$ を $⊔$ に消して左へ、状態 $h$ 。様相 $1111 h 1$

8 ステップ目で停止状態 $h$ に入ったので、 $M$ は停止する。途中で遷移が定義されていない組（「—」）には一度も出会っていない。

停止時のテープの内容は $11111$ （ $1$ が 5 個）であり、この機械は 1 進法で $3 + 2 = 5$ を計算していることがわかる。

よって、求めるステップ数は $8$ である。

別解

入力 $111 + 11$ はマス 1〜6 に書かれている（1,1,1,+,1,1）。マス 7 以降は $⊔$ である。ヘッドはマス 1、状態は $q_{0}$ から始める。

ステップ 1: マス 1 で $q_{0}$ 、記号 1 → $(q_{0}, 1, R)$ 。ヘッドはマス 2。
ステップ 2: マス 2 で $q_{0}$ 、記号 1 → ヘッドはマス 3。
ステップ 3: マス 3 で $q_{0}$ 、記号 1 → ヘッドはマス 4。
ステップ 4: マス 4 で $q_{0}$ 、記号 $+$ → $(q_{1}, 1, R)$ 。マス 4 を 1 に書き換え、ヘッドはマス 5。
ステップ 5: マス 5 で $q_{1}$ 、記号 1 → ヘッドはマス 6。
ステップ 6: マス 6 で $q_{1}$ 、記号 1 → ヘッドはマス 7。
ステップ 7: マス 7 で $q_{1}$ 、記号 $⊔$ → $(q_{2}, ⊔, L)$ 。ヘッドはマス 6。
ステップ 8: マス 6 で $q_{2}$ 、記号 1 → $(h, ⊔, L)$ 。状態 $h$ になる。

検算: $q_{0}$ で 1 を 3 個読み（3 ステップ）、 $+$ で 1 ステップ、 $q_{1}$ で 1 を 2 個読み（2 ステップ）、空白で 1 ステップ、 $q_{2}$ で 1 ステップ。合計 $3 + 1 + 2 + 1 + 1 = 8$ 。途中で未定義の遷移には到達しない。

よって 8 ステップ。

この問題の確認

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

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

確認の方法について

間違いを報告する

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

関連する問題

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

状態	読む記号	書く記号	ヘッドの移動	次の状態
$q_{0}$	$1$	$1$	$R$	$q_{0}$
$q_{0}$	$+$	$1$	$R$	$q_{1}$
$q_{1}$	$1$	$1$	$R$	$q_{1}$
$q_{1}$	$⊔$	$⊔$	$L$	$q_{2}$
$q_{2}$	$1$	$⊔$	$L$	$h$

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