当前课程知识点:软件理论基础 >  第十二章 Turing机 >  12.1 图灵机的介绍 >  Video

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

Video在线视频

下一节:Video

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

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

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

我是清华大学教师罗贵明

今天介绍第12章 图灵机

内容包括:图灵机的介绍

图灵机的定义

图灵机的即时描述

图灵机的计算

最后介绍,图灵机的编程

什么是图灵机

首先介绍语言的层次

语言是这门课中的核心

软件解决的对象

用语言来描述

开始我们给出正则语言

这些语言都是正则语言

它们可以用有限自动机表示

像DFA、NFA

{a的n次方 b的n次方}

回文

都不在正则语言里

这些语言是上下文无关语言

可以用下推自动机表示

{a的n次方 b的n次方 c的n次方}

{WW}

这样的语言,我们用泵引理证明了

不在上下文无关语言里

它们应该是哪种语言呢?

又能用哪种自动机描述呢?

这就是本章要讲的内容

图灵机的语言

表示这种语言的自动机叫图灵机

图灵机是由这样的带构成

在这带里,划分成一个个的单元

每个单元的符号

叫带符号

带符号里有一个特殊的符号

空白符B

在图灵机里

有一个控制单元

控制这读头

读、写一些字符

叫带头,也叫读头

读头

是用一个有限状态机控制

带两端无限长

读头读、写之后

它左移或者右移

所以读头的每一步

要做下面的这几个动作

第一,读一个符号

然后,写一个符号

第三步,左移或者右移

看例子

这是一个字符串

读头现在读a

然后把a写成k,再左移

这就完成了读头的功能

这个读头,现在读b

把b改写成f

然后右移

这完成了另外一个动作

对带符号,读头开始一般

位于带的最左边的位置

假定这串一定有字符

一般不能为空

读头的动作可以用状态描述

在状态q1

读a这个字符

然后把a改写成为b

再左移到新的状态q2

当然,也可以是右移

用r表示右移

转移可以用这种符号表示

也可以用这种符号表示

这个转移写成状态转移函数

状态转移函数是 q1、a

这是原来的

通过把a改成b

再右移之后,到新的状态q2

就写成这组关系

有限状态机

下推自动机

都有状态转移函数

大家注意

转移写成这样的形式

就是一个确定性的转移

对一个状态 、一个输入字母

转移最多只有一个

再看另外表示

q1读c, 把c改成d

左移之后到q2

左移也可以用这字符表示

箭头指那边

这样的状态转移函数

可以写成,在q1输入c

转移到 (q2、d、左移)

图灵机的转移

可以用这状态转移函数来描述

一个例题

带中有 abac 符号串

当前状态是 q1

在q1状态读a

把a要改成b 然后右移到 q2

完成这动作

得到了新的表示

就是完成了这一状态

把a改成b

然后右移

状态变为 q2

在q1状态读a

把a改成b,再左移到 q2

整个的描述:把a改成b,左移到 q2

也可以作这样的转移

在q1读的是B,空白符

把空白符改为字符g,右移到 q2

得到的是:空白符 B 改成 g,右移到 q2

刚才讲了,它是确定的,q1读a

把a换成b,右移到 q2

也可以 q1 读 b

这跟它不一样,读的是b

把b换成d,左移到q3

这转移在图灵机是可以的

哪种是不行的呢?

像q1读a,改成b,右移到 q2

同时,q1 还是读 a

状态转移函数右边

和这是一样的

都是把a改成d,再左移到 q3

这是不允许的

还不容许有 ε 转移

在图灵机

可以有部分转移函数

有的状态定义转移,像在q1

把 a 换成 b

右移到 q2

也可以 q1 读 b,换成d,左移到 q3

定义了转移,它就按这转移

也可以 q1 读 c

没给出状态转移

没状态转移函数

没有转移,就停机了

不再作任何转移

在图灵机是允许的

图灵机有哪些功能?

首先,它可以识别字符串

如同之前讲的

有限自动机,下推自动机

可以识别字符串

接受输入,当前的输入串输入完

落在图灵机的某一个终态

这个字符串就接受了

拒绝一个输入

表示这个输入串读时

停在某一个非终态

或者无限循环

这也是不接受的

如果接受的字符串

放在一个集合里

就是图灵机接受的语言

看一个例子

图灵机的表示

可以用状态转移图

这里有两个状态

状态的表示跟之前

有限自动机,下推自动机

的定义是类似的

这是初态,这是终态

转移的形式

跟前面定义的状态转移是一样的

由这状态转移图

定义的图灵机

它接受的串是什么?

由这些串

接受串,定义的语言是什么?

这图灵机

接受的语言是 aa*

也是 a 的正闭包

下面检验

给输入串 aaa

开始,图灵机处在初始状态

这个转移,读a

a 写成 a

还是到 q0 状态

得到是这样的

这是第一步操作

第二步

第二步,q0 读 a

按这转移,状态还是 q0

第三次,q0 读的是 a

还是按这样的状态转移

a写成a、右移到初始状态 q0

第四次,q0

读的是B

B 写成 B

左移到 q1 状态

q0读 B

B写成B,左移到 q1

落在q1

q1是终态

串读完了

再没有转移了,停机

这个串被接受

aaa 被接受了

再看另外一个输入串 aba

同样,在q0初始状态

q0 读a,a改写成a,右移

q0 读 b

这状态转移图

没有 q0 读 b 这个转移

自动机就停机了

这个串没读完

在一个非终态停机

因此,这个串被拒绝了

再看一个图灵机

这个图灵机由两个状态构成的

输入串 aba,非常简单

三个字符

在 q0

读 a

要执行这个状态转移

a不变、右移、到 q0 状态

q0 读 b

应该是这状态转移

q0 读 b, b 写成 b

左移到 q0 状态

q0 又读 a

再作这样的转移

a不变,右移到 q0

q0 再读 b

大家看

这样操作下去

是无限循环

不能到达终态

图灵机不能停机

这输入就不可能结束

我们介绍了

另外一种不被接受的情形

在这一节给出了图灵机的介绍

从这里大家可以了解图灵机

大致的功能

图灵机怎么定义?

怎么计算?

这是后面要介绍的内容

这节内容介绍完毕

谢谢大家

软件理论基础课程列表:

第一章 基础知识

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

也许你还感兴趣的课程:

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