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

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

Video在线视频

下一节:Video

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

Video课程教案、知识点、字幕

欢迎同学们来到《软件理论基础》MOOC课堂

现在介绍第三节

图灵机移动的扩展

标准图灵机读头

读完之后,左、右移动

这是一种移动

状态转移

从一个状态转到另外一个状态

也是移动

这两种移动能作哪些扩展呢?

读头移动增加一个功能

对这个带

读头读 a

可以左移、可以右移

还增加一种移动:不动

停止在这里

用 S 表示

例子

q1,正在读 a

把 a 改成 b,停在这里

之后

转到状态 q2

跟 q1 的位置一样

标准图灵机没有这样的操作

增加了一种功能之后

这类图灵机跟标准图灵机的功能是不是相同的?

定理

具有停止功能的图灵机

跟标准图灵机具有相同的功能

要证明这结论

第一个结论:具有停止功能的图灵机

具有标准图灵机的功能

标准图灵机能够做到的事

停止功能的图灵机也能做

因为具有停止选择功能图灵机

只要不使用停止功能

其它的跟标准图灵机是一致的

所以结论是显然的

另外,还有结论:

具有停止功能的图灵机

能做的事,标准图灵机也能做

这就证明了标准图灵机

模拟

具有停止功能的图灵机

具有停止功能的图灵机

读一个字符

写一个字符

左移动到新的状态

这跟标准图灵机是一样的

所以标准图灵机是能做的

右移动,也是一样

差异是哪呢?

具有停止功能的图灵机

能做这样的事

在 q1 状态读 a,改成 b,停止

然后到新的状态 q2

这是停止功能图灵机具有的特点

标准图灵机没有

标准图灵机是不是能

模拟这个动作呢?

可以这样模拟

q1 把 a 改成 b

首先左移到一个新的状态

用 \overline{q2} 表示

它读任何一个符号

还是写成这个符号

不变

然后,右移到新的状态 q2

中间作了一个辅助

完成了这个动作

x 是任意一个符号

它就可以模拟

具有停止功能的图灵机

看一个实例

q1 读 a

a 改成 b,不动

到 q2 状态

在停止功能图灵机

读 a

a 改成 b,不动到 q2

标准图灵机,按刚才的做法

q1 读 a,a 改成 b

首先,左移动到 \overline{q2}

\overline{q2} 读 b

b 不变

然后,右移动到

状态 q2

开始,这是一样的

结束,这跟这也是一样的

模拟

做到要的结果

当然,中间步数可能多一些,这没关系

只要达到相同的结果就可以了

这就是模拟的实质

具有停止选择的图灵机

跟标准图灵机的功能是相同的

下面介绍另一个移动扩展

状态转移的扩展

标准图灵机

状态转移每一次移动

只能一种,或者停机

或者一个转移

对这个功能进行扩展

有限自动机有 DFA、NFA

下推自动机

有PDA、DPDA

特别,下推自动机

DPDA 跟 PDA 是不等价的

对图灵机也做扩展

非确定图灵机

也有状态、输入字母

带符号,等等

只是状态转移有多种选择

状态转移函数定义为

(状态,带符号),二维

到幂集合,(状态,带符号,左右移)

构成幂集合的映射

是一个三元组的集合

有多种选择

这跟标准图灵机不一样了

是新的一类图灵机

它跟标准图灵机是不是功能相同的?

q1 读 a

a 改成 b,左移到 q2

还在 q1 读 a,把 a 改成 c,右移到 q3

这在标准图灵机是不行的

但非确定图灵机可以

非确定图灵机作这样的转移

一次移动

开始 q1 状态读 a

下一次

得到的第一个选择是这个结果

第二个选择是这样的结果

一次就得到这样的转移

在非确定图灵机

因为有多种选择

怎么是接受和拒绝?

一个字符串

表示的初始即时描述

如果在这图灵机

经过若干次的转移,能转移到这种形式

qf 是终态

叫做最终的即时描述

有一种实现能得到这样

w 就被接受

这是非确定图灵机的接受

下面有结论

非确定图灵机能模拟标准图灵机

确定图灵机

是非确定图灵机中

一种特殊的情形

确定图灵机

也是标准图灵机,能做到的事情

非确定图灵机一定能够做到

这个结论显然

接下来,标准图灵机

也是确定图灵机

能够模拟非确定图灵机

在带中保留所有可能的计算

用一个示意图

这是非确定图灵机

每一个分支表示一种计算

比如,状态 q1 到 q2、q4,等等

是第一个计算

另外,q1、q2、q5、q6

也是一种计算

记为第二种计算

还有其它的计算

非确定图灵机

用标准图灵机模拟

保留所有的计算路径

然后,把这些计算

都存在二维的带里

看这个例子

状态 q1 读 a,写成 b,左移到 q2

同样,状态 q1 读 a,改写成 c,右移到 q3

在非确定图灵机

开始读 a

写到二维

没有作任何移动时

开始状态 q1 读 a 得到的形式

在非确定中

第一个选择,a 改成 b,左移到 q2

第二种选择,a 换成 c,右移到 q3

这是非确定

把这种情形记在二维带里

bbc 记到这个通道

对应 q2 是这个位置

这里 cbc,对应状态 q3 在这个位置

每次计算都作这样的处理

有多种选择

每一次选择都作这样的复制

就得到标准图灵机

能够模拟非确定图灵机

每一次重复这样的步骤:

每一步执行一个计算

如果当前计算有两个或者多个选择

把之前结构都复制出来

然后,把复制的状态改变

重复这样的步骤,直到完成

用标准图灵机也能够模拟非确定图灵机

得到非确定图灵机

跟标准图灵机具有相同的功能

说明

功能是相同的

但它们的计算复杂性是不一样的

确定图灵机

要模拟非确定图灵机

时间应该是指数级

在计算复杂性中

还要作进一步地介绍

这一节介绍了

图灵机的另一种扩展

读头移动的扩展

原来只有左移和右移

增加停止不动

对图灵机的状态转移的移动

状态转移可以有多个选择

也就是非确定图灵机

我们证明了所有这些扩展

跟标准图灵机

功能都是相同的

这节内容介绍完毕

谢谢大家

软件理论基础课程列表:

第一章 基础知识

-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笔记与讨论

也许你还感兴趣的课程:

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