图灵机概述 例： X00Y 115 D 识别语言 L={0n1n|n≥1 的图灵机 有限 动作之前 的状况 识别000111的动作 控制器 δ(qo,0)-→(q1,X,R) δ(q1,0)-→(q1,0,R)〉 δ(g1,0)-→(q1,0,R) δ(q1,1)→(q2,Y,L) 有限 动作之后 δ(q2,0)-→(q4,0,L) 控制器 的状况 17
图 灵 机 概 述 • 例： 识别语言 L={0n1 n | n 1} 的图灵机 识别000111的动作 (q0 , 0)→(q1 , X, R) (q1 , 0)→(q1 , 0, R) (q1 , 0)→(q1 , 0, R) (q1 , 1)→(q2 , Y, L) (q2 , 0)→(q4 , 0, L) X 0 0 Y 1 1 b b … 有限 控制器 X 0 0 Y 1 1 b b … 有限 控制器 动作之前 的状况 动作之后 的状况 17
图灵机概述 例： X 00 Y 11bD 识别语言 L={0n1n|n≥1 的图灵机 有限 动作之前 的状况 识别000111的动作 控制器 δ(qo,0)-→(q1,X,R) δ(q1,0)-→(41,0，R)〉 δ(g1,0)-→(g10,R) δ(q1,1)-→(q2,Y,L δ(q2,0)-→(q4,0,L 有限 动作之后 控制器 的状况 δ(94,0)→(q4,0,L) 18
图 灵 机 概 述 • 例： 识别语言 L={0n1 n | n 1} 的图灵机 识别000111的动作 (q0 , 0)→(q1 , X, R) (q1 , 0)→(q1 , 0, R) (q1 , 0)→(q1 , 0, R) (q1 , 1)→(q2 , Y, L) (q2 , 0)→(q4 , 0, L) (q4 , 0)→(q4 , 0, L) X 0 0 Y 1 1 b b … 有限 控制器 X 0 0 Y 1 1 b b … 有限 控制器 动作之前 的状况 动作之后 的状况 18