形式语言自动机——图灵机二PPT学习教案.pptx

会计学
1
形式语言自动机——图灵机二
2
双向无穷带的图灵机与基本图灵机的等价
可以用一个双道的单向无穷带图灵机M1模拟具有双向无穷带的基本图灵机M.
当M的读写头从初始位置右移时，M1用上道模拟M
当M的读写头从初始位置左移时，M1用下道模拟M
M1的初始单元：[X0,￥],￥表示输入带最左单元。
M1的形式构造：
Q1={[q,U],[q,D]│q∈Q}∪{q1}
∑1={[I,J],[I,￥] │I,J∈∑,￥∑}
T1={Xi , B} │ Xi ∈T}
F1={[q,U],[q,D] │q∈F}
￥
第1页/共9页
3
多带图灵机
多带图灵机由一个有限控制器，n个读写头和n条双向无限带组成。
一次动作：
控制器状态转变
每个读写头在扫到的单元重写一个字符
各读写头各自向左/右移动一个单元（含不移动的情况）x
转移函数：
δ：Q×∑k →Q×∑k×{L,R,S}k k是带的个数
形如δ(qi , a1,a2,…,ak)=(qj,b1,b2,…,bk,L,R,…，L)
第2页/共9页
4
多带图灵机
定理：每个多带图灵机都有一个与之等价的单带图灵机.
假设M有k条带，
S将k条带的信息都存在它的一条带上，用新的符号#作为定界符，以分开不同带的内容。
此外，S还要记录读写头的位置，这里用符号加“点”来标记，S把它想象为虚拟读写头。（也可用双道+识别符）
第3页/共9页
5
非确定图灵机
下一个移动步有多种选择
转移函数可以为  : Q    2Q    D ，其中 Q、  和 D 分
别为有限状态集、带符号集和带头的移动方向. 即 (q,X)
为三元组的集合：
{ (q1 ,Y1 ,D1 ) , (q2 ,Y2 ,D2 ) , … , (qk ,Yk ,Dk ) }
非确定图灵机语言接受能力与（确定的）基本图灵机等价（证明略）
第4页/共9页
6
图灵机与计算机
以普通计算机模拟图灵机
以多带图灵机模拟普通计算机
第5页/共9页
7
以普通计算机模拟图灵机
采用适当的数据结构（如转移表）不难编制普通的计
算机程序实现图灵机的有限状态控制机制.