图灵机概述 例 000111bb 识别语言 L={01n≥1} 的图灵机 有限 策略:从左向右,控制器 轮番把带上最左的0和1分别写成X和Y(期间要向右 和向左移动读写头),直至全部写完 T=〈Q,r,b,Σ,q0,F,) Q={q0,q1,…,q5 F={0,1,b,X,Y ∑={0,1} F={5 6见下一页图 灵 机 概 述 • 例： 识别语言 L={0n1 n | n  1} 的图灵机 策略：从左向右， 轮番把带上最左的0和1分别写成X和Y（期间要向右 和向左移动读写头），直至全部写完 T= Q, , b, , q0 , F,   – Q = {q0 , q1 , …, q5 } −  = {0, 1, b, X, Y} –  = {0, 1} − F = {q5 } –  见下一页 0 0 0 1 1 1 b b … 有限 控制器 11