当前课程知识点:软件理论基础 >  第十二章 Turing机 >  12.3 图灵机的即时描述 >  Video

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

Video在线视频

下一节:Video

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

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

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

现在介绍第三节

图灵机的即时描述

图灵机有即时描述

在讲下推自动机的时候

介绍过即时描述

即时描述是

表示自动机的当前格局

图灵机的即时描述怎么给的呢?

给定一个图灵机

它的整个带以及状态

表示出来

这就是图灵机的当前格局

叫图灵机的即时描述

这里 q 是当前图灵机所处的状态

q 正扫描的

是它右边字符 Xi

我们对图灵机更关心的

它是怎么变化?

图灵机的推导关系

图灵机的推导关系

用这个符号表示

在下推自动机里也用这个符号表示

特指哪个图灵机M

就把M放在它的右下角

如果清楚了

转移是对哪个图灵机的

这个M可以省略

转移或者推导关系怎么给的呢?

假设在图灵机有这样的状态转移

q 状态读 Xi

Xi换为Y

左移到新的状态 p

这是图灵机的一个状态转移

下面看图灵机

它所处的一个即时描述是这种形式

q 状态正在读Xi

经过这状态转移

下一个即时描述是什么样?

Xi 改成 Y,然后左移

左移到这儿,状态变成 p

下一步的即时描述可以写成这种形式

是经过了状态转移

从这个即时描述得到这个即时描述

图灵机的即时描述

可以给出图灵机的

整个变化形式

这个定义

有两点

大家注意

第一:当 i 等于 1 时

q 在最左边

读这个, 改这个

然后左移

这即时描述左边是哪些符号?

空白符

空白符

一般在即时描述里不写的

但是,这里左移之后

状态读入的符号

应该是空白符

这个空白符不能省

必须要写

这是第一种情形

第二种

当 i 等于 n

也是最右边的符号

读了这个符号

改成 Y,左移

若 Y 是空白符

整个即时描述最右边

没写出来的都是空白符

这个空白符多余

可以去掉

即时描述

把 Xn 变为空白符

左移到 Xn-1 时

这个空白符省掉

再看另一个转移

状态转移是 q 读 Xi

Xi 变成 Y,右移

刚才是左移,这是右移

转到状态 p

原来的即时描述

经过这状态转移,Xi 变为 Y

然后右移,状态变为 p

这是新的即时描述

这里,同样两点情形

第一种,当 i 等于 n 时

i 等于n

Xn 变为 Y,右移

状态变成 p

p 在右边

Xn 右边

是空白符

状态要扫描一个符号

这个符号不能省

移到这里

空白符要写

当 i 等于 1

并且符号 Y 是空白符时

它是最左边一个符号

最左边符号换成空白符

这个空白符

可以去掉

不要

即时描述推导

是图灵机整个的变化

如果只考虑最后的结果

不考虑中间的变化过程

就谈到传递闭包

在图灵机

即时描述也可以定义传递闭包

定义形式

跟下推自动机的定义

一样

用递推的形式给出

图灵机的传递闭包

记成为“*”

如果图灵机已知

可以简记为这种形式

即时描述

以及它的传递闭包作什么用呢?

给一个图灵机

上一节讲过

这样一个字符串

通过图灵机识别

下面用即时描述识别这个字符串

初始状态,这个字符串写这里

经过状态转移

整个即时描述的

转移都可以写出来

有的是一步步写的

有的按它的传递闭包

从即时描述

在图灵机

最后推导出这个即时描述

这个即时描述有什么特点呢?

它是初始状态加上一个要识别的串

这个即时描述叫初始即时描述

这个即时描述它含有终态 q6

字符串里含有终态

这个即时描述

叫做最终即时描述

字符串表示的初始即时描述

在图灵机经过转移

能够转移到最终即时描述

这个字符串就被接受

否则不被接受

通过这个方法可以定义图灵机的语言

图灵机接受的语言

称为递归可枚举语言

给定图灵机

把这个串表示的即时描述

在图灵机里

经过转移,最后能够转移到这种形式

αpβ

其中 p 是终态

只要有这样的转移

这样的串

放在这个集合里

叫做图灵机接受的语言

其中这个即时描述

叫做图灵机的初始即时描述

这个即时描述叫做最终即时描述

在定义里

这个串是不是被图灵机接受

从最初的即时描述

能否转移到最终的即时描述

最终的即时描述

只给出了终态表示

没有说一定停机

什么是停机?

就是没状态转移

定理

任给一个图灵机

可以构造跟它等价的一个图灵机

原来图灵机 M 接受字符串

不一定停机

而构造等价的图灵机 M'

接受这字符串

而且停机

任何一个图灵机

这是对应的

以后我们再考虑

字符串被图灵机接受时

总是假定

它一定停机

在以后,我们只要提到图灵机

接受字符串

就表示这个字符串读完了

而且它在终态停机

假如串不属于这个图灵机

图灵机不能保证停机

像循环那个例子

它是无限循环的

所以不被接受

不能保证停机

下面介绍另外一个语言

递归语言

递归语言

是一个特殊的图灵机的语言

如果串属于这个图灵机

在图灵机里

被它接受了

这个图灵机会停机的

如果串不属于这个图灵机

也要求图灵机要停机

最后一定会停机

跟递归可枚举语言不一样

这个语言的限定条件更高

它要求任何一个串必须停机

递归语言对应的问题

以后要讲的

是可判定的问题

这节我们介绍了图灵机的一种表示

即时描述

就是当前的格局

给出了当前格局的转移

通过即时描述的转移

定义了图灵机的语言

就是递归可枚举语言

以及递归语言

这节内容介绍完毕

谢谢大家

软件理论基础课程列表:

第一章 基础知识

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

也许你还感兴趣的课程:

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