图灵机接受的语言 定义Vw∈∑,如果M从G=q开始的计算停机在 接受格局,则称M接受输入串w.M接受的语言LMD 是M接受的所有输入串,即LMO={w∈x|M接受w 例1(续)M关于输入w=10100的计算: q10100B}1q0100B}10g0100B}101q00B}1010g0B F101000BF1010g10BF101q20BB}101Bg3BB 由于停机在接受格局,故M接受10100 L(MO={v0|w∈{0,41}"} 1010 图灵机接受的语言 定义 wΣ* , 如果M从σ0= q0w开始的计算停机在 接受格局, 则称M接受输入串w. M接受的语言L(M) 是M接受的所有输入串, 即L(M)={wΣ* | M接受w}. 例1 (续) M关于输入w=10100的计算: q010100B ⊢ 1q00100B ⊢ 10q0100B ⊢ 101q000B ⊢ 1010q00B ⊢ 10100q0B ⊢ 1010q10B ⊢ 101q20BB ⊢ 101Bq3BB 由于停机在接受格局, 故M接受10100. L(M)={w00 | w{0,1}* }