文章目录
一、图灵机示例
二、图灵机示例 2
一、图灵机示例
指令 L : ( p , 1 ) → ( q , 0 , L ) \rm L : (p,1) \to (q, 0, L)L:(p,1)→(q,0,L)
初始状态下 , 状态是 p \rm pp 读取头 指向的字符是 1 11 , 如下图 :
执行完 L \rm LL 指令之后 , p \rm pp 状态变为 q qq 状态 , 读取头将指向的字符 1 11 擦除 , 改为 0 00 , 向左移动一个单位 ( 这里不进行移动 ) ;
左端点向左移动默认不动说明 :
一般情况下我们计算时涉及的图灵机都是 向右无限延长的带子 , 带子有一个左端点 ;
当读写头当前已经指向左端点时 , 如果再向左移动 , 此时默认不进行移动 ;
二、图灵机示例 2
任务 : 设计一个图灵机 , 给定输入之后 , 图灵机会 在输入中寻找 1 11 字符 ;
算法 :
如果 找到了 1 11 字符 , 就会将该字符转变成 0 00 字符 , 然后将当前状态改为接受状态 f \rm ff , 然后停下来 ;
如果带子上的字符都读取完毕后 , 没有找到 1 11 , 只找到了空白字符 , 将该空白字符改为 1 11 , 然后向左移动一格 , 然后停下来 ;
( 自动机停下的前提是处于可接受状态 )
根据上述算法 , 构造图灵机 ;
图灵机设计 :
① 状态集 Q = { q , f } \rm Q = \{ q , f \}Q={q,f} , 其中 q \rm qq 是开始状态 , f \rm ff 是接受状态 ;
② 输入字符集 Σ = { 0 , 1 } \rm \Sigma = \{ 0, 1 \}Σ={0,1} ;
③ 带子字符集 Γ = { 0 , 1 , B } \rm \Gamma = \{ 0, 1, B \}Γ={0,1,B} , 其中 B \rm BB 是空白字符 ;
④ 指令 δ ( q , 0 ) = ( q , 0 , R ) \rm \delta (q, 0) = (q, 0, R)δ(q,0)=(q,0,R)
⑤ 指令 δ ( q , 1 ) = ( f , 0 , R ) \rm \delta (q, 1) = (f, 0, R)δ(q,1)=(f,0,R)
⑥ 指令 δ ( q , B ) = ( q , 1 , L ) \rm \delta (q, B) = (q, 1, L)δ(q,B)=(q,1,L)
上述图灵机设计中 , 最关键的部分是三条指令 ;
图灵机处于开始状态 q \rm qq , 读头指向 0 00 字符 , 左端的 00 0 000 是输入字符 , 查看图灵机是否接受 00 0 000 字符串 ;
下面图灵机后续都是 B \rm BB 空白字符 ;
根据指令 指令 δ ( q , 0 ) = ( q , 0 , R ) \rm \delta (q, 0) = (q, 0, R)δ(q,0)=(q,0,R) , 当前状态 q \rm qq , 当前指向字符 0 \rm 00 , 输出内容是 q , 0 , R \rm q, 0, Rq,0,R ,
即 状态变为 q \rm qq , 读头指向的字符变为 0 \rm 00 , 向右移动一个字符 ;
如下图 :
此时继续 根据指令 指令 δ ( q , 0 ) = ( q , 0 , R ) \rm \delta (q, 0) = (q, 0, R)δ(q,0)=(q,0,R) , 当前状态 q \rm qq , 当前指向字符 0 \rm 00 , 输出内容是 q , 0 , R \rm q, 0, Rq,0,R ,
即 状态变为 q \rm qq , 读头指向的字符变为 0 \rm 00 , 向右移动一个字符 ;
如下图 :
此时继续 根据指令 指令 δ ( q , B ) = ( q , 1 , L ) \rm \delta (q, B) = (q, 1, L)δ(q,B)=(q,1,L) , 当前状态 q \rm qq , 当前指向字符 B \rm BB , 输出内容是 q , 1 , L \rm q, 1, Lq,1,L ,
即 状态变为 q \rm qq , 读头指向的字符变为 1 \rm 11 , 向左移动一个字符 ;
如下图 :
此时继续 根据指令 指令 δ ( q , 0 ) = ( q , 0 , R ) \rm \delta (q, 0) = (q, 0, R)δ(q,0)=(q,0,R) , 当前状态 q \rm qq , 当前指向字符 0 \rm 00 , 输出内容是 q , 0 , R \rm q, 0, Rq,0,R ,
即 状态变为 q \rm qq , 读头指向的字符变为 0 \rm 00 , 向右移动一个字符 ;
如下图 :
此时继续 根据指令 指令 δ ( q , 1 ) = ( f , 0 , R ) \rm \delta (q, 1) = (f, 0, R)δ(q,1)=(f,0,R) , 当前状态 q \rm qq , 当前指向字符 1 \rm 11 , 输出内容是 f , 0 , R \rm f, 0, Rf,0,R ,
即 状态变为 f \rm ff , 读头指向的字符变为 0 \rm 00 , 向右移动一个字符 ;
此时的状态 f \rm ff 是接受状态 , 自动机停止运行 ;
如下图 :
图灵机 与 自动机 接受的条件是不同的 ;
图灵机计算过程中 , 一旦到达接受状态 , 立刻停机 , 不再继续进行计算 ; 并且称该图灵机是可接受的 ;
自动机即使到达接受状态 , 也要把自动机读取的字符读取完毕 , 才停止计算 ; 然后在查看最终的状态是否是接受状态 ;
