当前课程知识点:软件理论基础 > 第十三章 图灵机的扩展 > 13.4 受限图灵机 > Video
欢迎同学们来到《软件理论基础》MOOC课堂
现在介绍第四节
受限图灵机
标准图灵机的带
作另外一个改进
标准图灵机的带两端无限
现在读头
在某一个位置,初始位置吧
它的左端没有单元
右端无限
对这样一种图灵机
叫做半无限带机或者受限图灵机
这图灵机的模型是
读头在带
读 X1 这个地方
左边没有
最右边是无限延伸的
这种图灵机跟标准图灵机有哪些关系呢?
我们的结论是
标准图灵机可以模拟半无限带机
因为半无限带机,这边没有
这边跟标准图灵机一样
标准图灵机只用右半边
左边不用
这样,半无限带机能做的事
标准图灵机也能做
所以标准图灵机可以模拟半无限带机
反过来,半无限带机
就是受限图灵机
也能模拟标准图灵机
标准图灵机带两端无限
读头正在读 a
标准图灵机
中间做一分界线,把它分开
假设这个地方,分界线分开
分成右边部分
左边部分
右边部分还是按这样位置
而左边部分在分界线
旋转180度
连接到右边部分的下方
就得到两个通道的半无限带机
这是分界线
这是右边的部分
这是左边的部分
从这里向左,旋转之后是向右了
方向改变了
这就是一个两通道的半无限带机
跟一条带的半无限带机一样
读头读的是一个向量
写一个向量
左移或右移
这里读 a
这里读的是(B,a)向量
这是整个带
通道分带的右部和带的左部
它的状态也有变化
标准图灵机,状态 q1、q2
在半无限带机
状态分成两类
读分界线左边字符的状态
用左边的状态表示
就是q1L,等等表示左边的状态
读右边字符的状态
在半无限带机
用 q1R
表示半无限带机的状态
看一个例子
标准图灵机
q1 读 a,a 改成 g,右移到 q2
在半无限带机中
a 在分界线的右边
用右部转移
q1R 是右边的状态
读 (a,x),把它写成为 (g,x)
这 x 是一样的
是任何一个符号,右移到 q2R
这是右边的状态
如果 a 在分界线的右边
转移是这样的
如果 a 在分界线的左边
转移状态是 q1L
读的是 a
上面通道里 x 是任何一个带符号
a 改成 g
而 x 不做任何变化
注意,原来在标准图灵机右移
它在分界线的左边
这里变成左移了
到新的状态 q2L
其中 x 是任意的符号
这个标准图灵机 q1 读 a
a 在分界点的左边
两通道的半无限带机
就是左边状态 q1L
读的是字符 (B,a) 向量
如果转移,在标准图灵机
a 换成 g,右移到 q2 状态
在标准图灵机 q1 读 a
a 改成 g,右移
这是标准图灵机做到的
在两个通道
半无限机转移
读的是 (B,a)
这是左边状态
a 改成 g
上面符号 B 不变
这里右移,它就左移得到这个结果
半无限带机
模拟了标准图灵机
大家注意
这里有一个分界点 (#,#)
分界点状态有左、右之分
到了分界点 (#,#)
有这样的转移
q1R,分界点不变
右移
从右部状态转到左部状态
当然,也可以写右部状态
还有,左部的状态读 (#,#),不变
右移到了右部状态
当然也可以到左部状态
这说明,在分界点 (#,#) 它是一个非确定的
在端点
q1L 左部状态,读端点字符
不变
右移
原来左部状态就跳到右边状态
当然也可以是左部状态,是非确定的
非确定跟确定的功能完全一样
因此,有结论
半无限带机与标准图灵机
具有相同的功能
这节我们介绍了另外一类图灵机
半无限带图灵机或者受限图灵机
证明了这类图灵机
跟标准图灵机也是等价的
在下一节,讨论图灵机
与其他自动机的关系时
要用到这一类的图灵机
这节内容介绍完毕
谢谢大家
-1.1 概要
--第一节
-1.2 数学基础
--Video
-1.3 图
--Video
-1.4 证明方法
--Video
-1.5 语言基础
--Video
-1.6 语言运算
--Video
-习题--作业
-2.1 确定有限自动机的概念
--Video
-2.2 确定有限自动机的定义
--Video
-2.3 扩展转移函数
--Video
-2.4 正则语言
--Video
-2.5 DFA构造
--Video
-习题--作业
-3.1 非确定有限自动机的概念
--Video
-3.2 e转移
--Video
-3.3 非确定有限自动机的定义
--Video
-3.4 扩展转移函数
--Video
-3.5 等价性证明
--Video
-3.6 文本搜索
--Video
-习题--作业
-4.1 单一终结状态的NFA
--Video
-4.2 正则语言的运算性质
--Video
-4.3 正则表示和语言
--Video
-4.4 正则表示和正则语言
--Video
-4.5 正则语言的同态
--Video
-4.6 正则表示的代数定律
--Video
-习题--作业
-5.1 文法
--Video
-5.2 线性文法
--Video
-5.3 正则文法与正则语言
--Video
-5.4 自动机的积
--Video
-习题--作业
-6.1 基本问题
--Video
-6.2 泵引理
--Video
-6.3 非正则语言的判定 1
--Video
-6.4 非正则语言的判定 2
--Video
-6.5 DFA的优化 1
--Video
-6.6 DFA的优化 2
--Video
-习题--作业
-7.1 上下文无关文法
--Video
-7.2 规约和推导
--Video
-7.3 语法分析树
--Video
-7.4 规约、推导和语法分析树之间的关系
--Video
-7.5 上下文无关语言
--Video
-习题--作业
-8.1 CFG的应用
--Video
-8.2 CFG的转化
--Video
-8.3 文法二义性
--Video
-8.4 二义性的消除方法
--Video
-8.5 CFG的构造方法
--Video
-8.6 CFG的构造实例
--Video
-第八章 CFG的应用与文法的二义性--习题
-9.1 PDA介绍
--Video
-9.2 PDA的定义
--Video
-9.3 PDA的即时描述
--Video
-9.4 PDA的语言
--Video
-9.5 PDA与CFG的关系
--Video
-习题--作业
-10.1 确定下推自动机
--Video
-10.2 DPDA与其他语言的关系
--Video
-10.3 终态型DPDA和空栈型DPDA
--Video
-10.4 消除无用符号
--Video
-10.5 消除e产生式
--Video
-10.6 消除单一产生式
--Video
-10.7 CFG的化简与Chomsky范式
--Video
-习题--作业
-11.1 CFL的必要条件
--Video
-11.2 CFL的Pumping引理
--Video
-11.3 CFL的闭运算性质
--Video
-11.4 CFL的同态性质
--Video
-11.5 CFL的交运算
--Video
-11.6 CFL的判定性质
--Video
-习题--作业
-12.1 图灵机的介绍
--Video
-12.2 图灵机的定义
--Video
-12.3 图灵机的即时描述
--Video
-12.4 图灵机的计算
--Video
-12.5 图灵机的编程技术
--Video
-习题--作业
-13.1 Turing理论
--Video
-13.2 图灵机带的扩展
--Video
-13.3 图灵机移动的扩展
--Video
-13.4 受限图灵机
--Video
-13.5 图灵机与其他自动机
--Video
-习题--作业
-14.1 图灵机编码
--Video
-14.2 对角线语言与通用语言
--Video
-14.3 图灵机语言的性质
--Video
-14.4 判定问题和语言
--Video
-14.5 计算复杂性问题
--Video
-第十四章 不可判定问题--习题
-15.1 时间自动机
--Video
-15.2 Buchi自动机
--Video
-15.3 软件形式化验证
--Video
-15.4 模型检测方法
--Video
-15.5 M3C模型检测系统
--Video
-习题--作业
-期中考试