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

両側に無限に続くテープを 1 本もつ決定性チューリング機械 $M$ を考える。

• 状態の集合は $\{q_0,q_1,h\}$ である。初期状態は $q_0$、停止状態は $h$ である。$h$ からの遷移はなく、$M$ は $h$ に入った時点で停止する。
• 入力アルファベットは $\Sigma =\{0,1\}$、テープ記号の集合は $\Gamma =\{0,1,\bigsqcup \}$ である（$\bigsqcup$ は空白記号）。
• 遷移関数 $\delta$ は次の表で与えられる。表の各欄の $(p,c,D)$ は「状態 $p$ に移り、ヘッドの位置のマスに記号 $c$ を書き、ヘッドを向き $D$ に 1 マス動かす」ことを表す（$\mathrm{R}$ は右、$\mathrm{L}$ は左）。

はじめ、テープには入力文字列 $1011$ が左から順に連続する 4 マスに書かれ、それ以外のマスはすべて空白記号 $\bigsqcup$ である。ヘッドは入力の最も左の文字（左端の $1$）のマスにあり、状態は $q_0$ である。

遷移を 1 回行うことを 1 ステップと数える（$h$ に入る遷移も 1 ステップに数える）。$M$ が停止するまでのステップ数を求めよ。

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

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

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

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

• 入力アルファベット: $\Sigma =\{1,+\}$
• テープ記号の集合: $\Gamma =\{1,+,\bigsqcup \}$（$\bigsqcup$ は空白記号）
• 状態の集合: $\{q_0,q_1,q_2,h\}$。初期状態は $q_0$、停止状態は $h$ である（$h$ からの遷移はない）。
• テープは右に無限に続き、はじめは左端のマスから順に入力文字列が書かれ、残りのマスはすべて $\bigsqcup$ である。ヘッドは左端のマス（入力の 1 文字目）にあり、状態は $q_0$ である。

遷移関数 $\delta$ は次の表で与えられる。表の $(p,c,D)$ は「状態 $p$ に移り、いま読んでいるマスに記号 $c$ を書き、ヘッドを $D$ の向き（$R$ は右、$L$ は左）に 1 マス動かす」ことを表す。「—」の組では遷移は定義されていない。

遷移を 1 回適用することを 1 ステップと数える。入力文字列 $111+11$ を与えて $M$ を動かしたとき、状態が $h$ になるまでに何ステップかかるか求めよ。

両側に無限に続くテープを 1 本もつ決定性チューリング機械 $M$ を考える。

• 状態の集合: $\{q_0,q_1,q_2,q_3,h\}$。初期状態は $q_0$、停止状態は $h$（$h$ からの遷移はなく、$h$ に入った時点で $M$ は停止する）
• 入力アルファベット: $\{1\}$、テープ記号の集合: $\{1,\bigsqcup \}$（$\bigsqcup$ は空白記号）
• 遷移関数 $\delta$ は次の表で与えられる。表の「(書く記号, ヘッドの移動, 次の状態)」で、$\mathrm{R}$ は右へ 1 マス、$\mathrm{L}$ は左へ 1 マス動くことを表す。

$n$ を 0 以上の整数とする。はじめ、テープには連続する $n$ マスに $1$ が書かれ（入力 $1^n$）、それ以外のマスはすべて $\bigsqcup$ である。ヘッドは入力の左端のマス（$n=0$ のときは任意の 1 マス）にあり、状態は $q_0$ である。

遷移関数を 1 回適用することを 1 ステップと数える（$h$ に入る遷移も 1 ステップに数える）。入力 $1^n$ に対して $M$ が停止するまでのステップ数を $n$ の式で求めよ。

右方向に無限に続くテープを 1 本もつ決定性チューリング機械 $M$ を考える。

• 入力アルファベット: $\Sigma =\{1,+\}$
• テープ記号の集合: $\Gamma =\{1,+,\bigsqcup \}$（$\bigsqcup$ は空白記号）
• 状態の集合: $\{q_0,q_1,q_2,h\}$。初期状態は $q_0$、停止状態は $h$ である。$h$ からの遷移はなく、$M$ は状態 $h$ に入った時点で停止する。
• 遷移関数 $\delta$ は次の表のとおりである。$\delta (q,s)=(q^{\prime },s^{\prime },D)$ は「状態 $q$ でヘッドが記号 $s$ を読んでいるとき、そのマスに $s^{\prime }$ を書き、ヘッドを $D$ の向き（$\mathrm{R}$ は右へ 1 マス、$\mathrm{L}$ は左へ 1 マス）に動かし、状態を $q^{\prime }$ にする」という意味である。表にない組は、以下の計算では現れない。

最初、テープの左端から順に入力 $11+111$ が書かれ、それより右のマスはすべて $\bigsqcup$ である。ヘッドは左端のマス（入力の 1 文字目）にあり、状態は $q_0$ である。遷移を 1 回行うことを 1 ステップと数えるとき、$M$ が停止するまでのステップ数を求めよ。