图灵机概述 例 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
图灵机概述 例 000111bb 识别语言 L={01n≥1} 的图灵机 有限 动作之前 识别00151制器 的状况 δ(q,0)→>(q1,X,R) x00111bb ●● 有限 动作之后 控制器 的状况
图 灵 机 概 述 • 例： 识别语言 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
图灵机概述 例 X|0011bb 识别语言 L={01n≥1} 的图灵机 有限 动作之前 控制器 的状况 识别000111的动作 6(q0,0)→>(q1,X,R) 6(q1,0)-(q1,0,R) x00111bb 有限 动作之后 控制器 的状况
图 灵 机 概 述 • 例： 识别语言 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
图灵机概述 例 X|0011bb 识别语言 L={01n≥1} 的图灵机 有限 动作之前 的状况 识别000111的动作 控制器 6(q0,0)→>(q1,X,R) 6(q1,0)-(q1,0,R) x00111bb 6(q1,0)-(q1,0,R) 有限 动作之后 控制器的状况
图 灵 机 概 述 • 例： 识别语言 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
图灵机概述 例 X|0011bb 识别语言 L={01n≥1} 的图灵机 有限 动作之前 识别000111的动作 控制器的状况 6(q0,0)→>(q1,X,R) 6(q1,0)-(q1,0,R) x00y11bb ●● 6(q1,0)-(q1,0,R) 6(q1,1)-(q2,Y,L) 有限 动作之后 控制器 的状况
图 灵 机 概 述 • 例： 识别语言 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