当前课程知识点:软件理论基础 >  第十三章 图灵机的扩展 >  13.4 受限图灵机 >  Video

返回《软件理论基础》慕课在线视频课程列表

Video在线视频

下一节:Video

返回《软件理论基础》慕课在线视频列表

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

-习题--作业

第六章 正则语言的性质与DFA优化

-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

-习题--作业

第八章 CFG的应用与文法的二义性

-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

-习题--作业

第十章 下推自动机与CFG化简规范

-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

-习题--作业

第十二章 Turing机

-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

-习题--作业

期中考试

-期中考试

Video笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。