图灵机概述 例： 000111bb 识别语言 L={0n1n|n≥1} 的图灵机 有限 控制器 δ(qo,0)→(q1,X,R) δ(q2,0)→(g4,0,L 8(q1,0)-→(g1,0,R) δ(q4,0)-→(q4,0,L) δ(q1,)-→(q1,Y,R 8(q4,X-→(qo,X,R) δ(g1,1)-→(g2,Y,L) δ(q3,-→(q3,Y,R) δ(q2,-→(q2,Y,L δ(q3,B)→(q5,Y,R) δ(q2,X)→(q3,X,R) 12
图 灵 机 概 述 • 例： 识别语言 L={0n1 n | n 1} 的图灵机 (q0 , 0)→(q1 , X, R) (q2 , 0)→(q4 , 0, L) (q1 , 0)→(q1 , 0, R) (q4 , 0)→(q4 , 0, L) (q1 , Y)→(q1 , Y, R) (q4 , X)→(q0 , X, R) (q1 , 1)→(q2 , Y, L) (q3 , Y)→(q3 , Y, R) (q2 , Y)→(q2 , Y, L) (q3 , B)→(q5 , Y, R) (q2 , X)→(q3 , X, R) 0 0 0 1 1 1 b b … 有限 控制器 12
图灵机概述 。例： 000111bb 识别语言 L={0n1n|n≥1 的图灵机 有限 动作之前 控制器 的状况 识别000111的动作 δ(qo,0)-→(g1,X,R) X00111bb 有限 动作之后 控制器 的状况 13
图 灵 机 概 述 • 例： 识别语言 L={0n1 n | n 1} 的图灵机 识别000111的动作 (q0 , 0)→(q1 , X, R) 0 0 0 1 1 1 b b … 有限 控制器 X 0 0 1 1 1 b b … 有限 控制器 动作之前 的状况 动作之后 的状况 13
图灵机概述 例： X00111bb 识别语言 L={0n1n|n≥1 的图灵机 有限 动作之前 控制器 的状况 识别000111的动作 δ(qo,0)-→(g1,X,R) δ(q1,0)-→(41,0，R) X00111bb 有限 动作之后 控制器 的状况 14
图 灵 机 概 述 • 例： 识别语言 L={0n1 n | n 1} 的图灵机 识别000111的动作 (q0 , 0)→(q1 , X, R) (q1 , 0)→(q1 , 0, R) X 0 0 1 1 1 b b … 有限 控制器 X 0 0 1 1 1 b b … 有限 控制器 动作之前 的状况 动作之后 的状况 14
图灵机概述 例： X00111bb 识别语言 L={0n1n|n≥1 的图灵机 有限 动作之前 的状况 识别000111的动作 控制器 δ(qo,0)-→(q1,X,R) δ(q1,0)-→(q1,0,R) X00111bb δ(g1,0)-→(q1,0,R) 有限 动作之后 控制器 的状况 15
图 灵 机 概 述 • 例： 识别语言 L={0n1 n | n 1} 的图灵机 识别000111的动作 (q0 , 0)→(q1 , X, R) (q1 , 0)→(q1 , 0, R) (q1 , 0)→(q1 , 0, R) X 0 0 1 1 1 b b … 有限 控制器 X 0 0 1 1 1 b b … 有限 控制器 动作之前 的状况 动作之后 的状况 15
图灵机概述 例： X00111bb 识别语言 L={0n1n|n≥1 的图灵机 有限 动作之前 的状况 识别000111的动作 控制器 δ(qo,0)-→(q1,X,R) δ(q1,0)-→(q1,0,R)〉 δ(q1,0)-→(g1,0,P) δ(q1,1)→(q2,Y,L) 有限 动作之后 控制器 的状况 16
图 灵 机 概 述 • 例： 识别语言 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) X 0 0 Y 1 1 b b … 有限 控制器 X 0 0 1 1 1 b b … 有限 控制器 动作之前 的状况 动作之后 的状况 16