2. チューリングマシン作成練習

以下のチューリングマシンを作成してみましょう．（ヒント：教科書図6.6の問題の場合には，出力する文字は「c」の1種類だけでしたが，2種類以上の文字を出力することもできます．たとえば，2つの文字列を比較する問題で前の文字列を処理する際は「c」，後ろの文字列を処理する際は「d」を出力することで問題を解きやすくなる場合があります．）

Exercise t1: aⁿbⁿ

文字「a」と「b」からなる長さ2以上の文字列 x が入力された時に，いくつかの連続した「a」の後に同数の「b」が続く文字列である場合に終了状態で停止するチューリングマシンを作成しなさい．

ab -> 受理
abab -> 拒否
aaab -> 拒否
bbaa -> 拒否
aabb -> 受理
aaabb -> 拒否
aaabbb -> 受理

Exercise t2: equal

文字「a」を0, 文字「b」を1の代わりに使います．正の整数 x と y を2進数で表し（最上位は必ず「b」(1の代わり)），文字列をそれぞれ s_x, s_y とします．文字列 s_xcs_y を入力として，x = y の時にのみ終了状態で停止するチューリングマシンを作成しなさい（x, y の文字列表現は一意に表せるので，文字列として s_xとs_y が等しいと判定することができます）．

bbcbaa -> 拒否 (3 != 4)
bbbcbaa -> 拒否 (7 != 4)
babcbab -> 受理 (5 == 5)
bcb -> 受理 (1 == 1)

Exercise t3: greater

文字「a」を0, 文字「b」を1の代わりに使います．正の整数 x と y を2進数で表し（最上位は必ず「b」(1の代わり)），文字列をそれぞれ s_x, s_y としなさい．文字列 s_xcs_y を入力として，x > y の時にのみ終了状態で停止するチューリングマシンを作成しなさい．

bbcbaa -> 拒否 (11(2) = 3 < 4 = 100(2))
bbbcbaa -> 受理 (111(2) = 7 > 4 = 100(2))
babcbab -> 拒否 (101(2) = 5 = 101(2))
baaacbbb -> 受理 (1000(2) = 8 > 7 = 111(2))