图灵机概述 例 000111bb 识别语言 L={01n≥1} 的图灵机 有限 控制器 6(q,0)→>(q1,X,R)(q2,0)->(q4,0,D) 6(q1,0)-(q1,0,R)(q4,0)-→>(q4,0,L) 8(q1,1)→>(q1,Y,R)d(q4,X3-(q0,X,R) 8(q1,1)-(q2,Y,D)d(q3,Y)→>(q3,Y,R) 6(q2,1)→>(q2,Y,L)d(q3,B)-(5,Y,R) δ(q2,X)->(q3X,R图 灵 机 概 述 • 例： 识别语言 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