سلام
۲/ بر روی نوار دو رشته و بعد آنها یک عدد وجود دارد. ماشین تورینگی طراحی کنید که مشخص کند آیا در صورت تکرار رشته اول به اندازه عدد، آیا رشته دوم حاصل می شود یا نه.
نماد خانه ی blank را صفر و نماد رشته ها را a,b و عدد را به صورت یکانی فرض کرده ام:
[tex]\delta(q_0,\: a)=\: (q_0,\: a,\: R)[/tex]
[tex]\delta(q_0,\: b)=\: (q_0,\: b,\: R)[/tex]
[tex]\delta(q_0,\: 0)=\: (q_0,\: 0,\: R)[/tex]
[tex]\delta(q_0,\: 1)=\: (q_00,\: x,\: R)[/tex]
[tex]\delta(q_00,\: 1)=\: (q_1,\: x,\: L)[/tex]
[tex]\delta(q_1,\: x)=\: (q_1,\: x,\: L)[/tex]
[tex]\delta(q_1,\: 0)=\: (q_2,\: 0,\: L)[/tex]
[tex]\delta(q_2,\: a)=\: (q_2,\: a,\: L)[/tex]
[tex]\delta(q_2,\: b)=\: (q_2,\: b,\: L)[/tex]
[tex]\delta(q_2,\: 0)=\: (q_3,\: 0,\: L)[/tex]
[tex]\delta(q_3,\: a)=\: (q_4,\: a',\: L)[/tex]
[tex]\delta(q_3,\: b)=\: (q_5,\: b',\: L)[/tex]
[tex]\delta(q_4,\: a)=\: (q_4,\: a,\: L)[/tex]
[tex]\delta(q_5,\: a)=\: (q_5,\: a,\: L)[/tex]
[tex]\delta(q_4,\: b)=\: (q_4,\: b,\: L)[/tex]
[tex]\delta(q_5,\: b)=\: (q_5,\: b,\: L)[/tex]
[tex]\delta(q_4,\: a'')=\: (q_4,\: a'',\: L)[/tex]
[tex]\delta(q_5,\: a'')=\: (q_5,\: a'',\: L)[/tex]
[tex]\delta(q_4,\: b'')=\: (q_4,\: b'',\: L)[/tex]
[tex]\delta(q_5,\: b'')=\: (q_5,\: b'',\: L)[/tex]
[tex]\delta(q_4,\: 0)=\: (q_6,\: a'',\: R)[/tex]
[tex]\delta(q_5,\: 0)=\: (q_6,\: b'',\: R)[/tex]
[tex]\delta(q_6,\: a)=\: (q_6,\: a,\: R)[/tex]
[tex]\delta(q_6,\: b)=\: (q_6,\: b,\: R)[/tex]
[tex]\delta(q_6,\: a'')=\: (q_6,\: a'',\: R)[/tex]
[tex]\delta(q_6,\: b'')=\: (q_6,\: b'',\: R)[/tex]
[tex]\delta(q_6,\: 0)=\: (q_6,\: 0,\: R)[/tex]
[tex]\delta(q_6,\: a')=\: (q_3,\: a',\: L)[/tex]
[tex]\delta(q_6,\: b')=\: (q_3,\: b',\: L)[/tex]
[tex]\delta(q_3,\: a'')=\: (q_7,\: a,\: L)[/tex]
[tex]\delta(q_3,\: b'')=\: (q_7,\: b,\: L)[/tex]
[tex]\delta(q_7,\: a'')=\: (q_7,\: a,\: L)[/tex]
[tex]\delta(q_7,\: b'')=\: (q_7,\: b,\: L)[/tex]
[tex]\delta(q_7,\: 0)=\: (q_7,\: 0,\: R)[/tex]
[tex]\delta(q_7,\: a)=\: (q_7,\: a,\: R)[/tex]
[tex]\delta(q_7,\: b)=\: (q_7,\: b,\: R)[/tex]
[tex]\delta(q_7,\: a')=\: (q_7,\: a,\: R)[/tex]
[tex]\delta(q_7,\: b')=\: (q_7,\: b,\: R)[/tex]
[tex]\delta(q_7,\: x)=\: (q_8,\: x,\: R)[/tex]
[tex]\delta(q_8,\: x)=\: (q_8,\: x,\: R)[/tex]
[tex]\delta(q_8,\: 1)=\: (q_1,\: x,\: L)[/tex]
[tex]\delta(q_8,\: 0)=\: (q_9,\: 0,\: L)[/tex]
[tex]\delta(q_9,\: x)=\: (q_9,\: x,\: L)[/tex]
[tex]\delta(q_9,\: 0)=\: (q_10,\: 0,\: L)[/tex]
[tex]\delta(q_10,\: a)=\: (q_11,\: a',\: L)[/tex]
[tex]\delta(q_10,\: b)=\: (q_12,\: b',\: L)[/tex]
[tex]\delta(q_11,\: a)=\: (q_11,\: a,\: L)[/tex]
[tex]\delta(q_11,\: b)=\: (q_11,\: b,\: L)[/tex]
[tex]\delta(q_12,\: a)=\: (q_12,\: a,\: L)[/tex]
[tex]\delta(q_12,\: b)=\: (q_12,\: b,\: L)[/tex]
[tex]\delta(q_11,\: 0)=\: (q_13,\: 0,\: L)[/tex]
[tex]\delta(q_12,\: 0)=\: (q_14,\: 0,\: L)[/tex]
[tex]\delta(q_13,\: a)=\: (q_15,\: a'',\: R)[/tex]
[tex]\delta(q_14,\: b)=\: (q_15,\: b'',\: R)[/tex]
[tex]\delta(q_13,\: a'')=\: (q_13,\: a'',\: L)[/tex]
[tex]\delta(q_13,\: b'')=\: (q_13,\: b'',\: L)[/tex]
[tex]\delta(q_14,\: a'')=\: (q_14,\: a'',\: L)[/tex]
[tex]\delta(q_14,\: b'')=\: (q_14,\: b'',\: L)[/tex]
[tex]\delta(q_15,\: a)=\: (q_15,\: a,\: R)[/tex]
[tex]\delta(q_15,\: b)=\: (q_15,\: b,\: R)[/tex]
[tex]\delta(q_15,\: a'')=\: (q_15,\: a'',\: R)[/tex]
[tex]\delta(q_15,\: b'')=\: (q_15,\: b'',\: R)[/tex]
[tex]\delta(q_15,\: 0)=\: (q_15,\: 0,\: R)[/tex]
[tex]\delta(q_15,\: a')=\: (q_10,\: a',\: L)[/tex]
[tex]\delta(q_15,\: b')=\: (q_10,\: b',\: L)[/tex]
[tex]\delta(q_10,\: 0)=\: (q_F,\: 0,\: L)[/tex]