2018年04月13日

平成29年度 技術士第二次試験問題 情報工学部門 T−13

T−13
チューリングマシンのシミュレータにおいて、オートマトンとテープが与えられている。
これを実行して停止状態になったときのテープの値として、最も適切なものは
どれか。ここで、文字 b は空白を、状態 h は停止を意味し、最初のへッド位置と
内部状態は図に示すとおりとする。

[オートマトン]

┌─────┬─────┬─────┬─────┬─────┐
│ 現在の │ 現在の │ テープに │  次の  │  移動  │
│ 内部状態 │テープの値│ 書込む値 │ 内部状態 │  方向  │
├─────┼─────┼─────┼─────┼─────┤
│  0  │  b  │  1  │  1  │  R  │
├─────┼─────┼─────┼─────┼─────┤
│  0  │  0  │  1  │  1  │  R  │
├─────┼─────┼─────┼─────┼─────┤
│  0  │  1  │  0  │  0  │  L  │
├─────┼─────┼─────┼─────┼─────┤
│  1  │  b  │  b  │  h  │  L  │
├─────┼─────┼─────┼─────┼─────┤
│  1  │  0  │  0  │  1  │  R  │
├─────┼─────┼─────┼─────┼─────┤
│  1  │  1  │  1  │  1  │  R  │
└─────┴─────┴─────┴─────┴─────┘

[テープ]

 ┌─┬─┬─┬─┬─┬─┬─┬─┬─┐
 │b│b│b│1│1│1│1│b│b│
 └─┴─┴─┴─┴─┴─┴─┴─┴─┘
              △
             ┌─┐
             │0│
             └─┘
             ヘッド

 @ b b b 0 0 0 0 b b
 A b b b 1 1 1 0 b b
 B b b b 0 1 1 1 b b
 C b b 1 0 0 0 0 b b
 D b b 1 1 1 1 0 b b



続きを読む
posted by ファーストマクロ at 08:32| Comment(0) | H29技術士二次試験(情報工学)