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

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

Video在线视频

下一节:Video

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

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

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

现在介绍第二节:图灵机的定义

之前我们讲有限自动机,像DFA、NFA

讲下推自动机

都给出了这些自动机的形式化定义

根据前面介绍图灵机

大致的轮廓

也要给出图灵机的形式化定义

它可以描述成为七元组

Q 是状态集合

∑ 是输入字母的集合

γ 是带符号集合

δ 是状态转移函数

q0 是开始状态

B 是空白符

F 是终态集合

q0 是一个初始状态

它属于状态集中的一个状态

∑ 输入字母,包含在带符号集合里

B是带符号中的空白符

是一个特殊的符号

它不属于输入字母

F是状态集合的子集

最重要的是状态转移函数

状态转移函数δ:是由状态和带符号

到(状态、带符号、左右移)

三元组的映射

是一个确定性的映射

看这样表示的一个图灵机

这图灵机

有 {q0、q1、q2、q3、q4}

五个状态

输入字母是 a 和 b

带符号是a、b、x、y,还有空白符 B

终态是q4

它接受什么样的语言呢?

这个图灵机它接受的语言

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

这个语言

不是正则语言

但它是下推自动机接受的语言

或者是上下无关语言

图灵机是不是接受这个语言?

给字符串 aabb

看这图灵机是怎么运作的

首先,在 q0

读 a

q0 读 a

执行这个状态转移

把 a 写成 x,右移到 q1

q0读a,a写成x,右移

在q1,读 a

执行的转移是把 a 写成 a

右移到q1状态

q1 读 b

执行这一个状态转移

把 b 写成 y,左移到 q2 状态

q2 读 a

执行这个状态转移

a 写成 a,左移,还是 q2 状态

q2 读的 x,执行这个转移

x 写成 x,右移到 q0

q0,回来了,读a

按之前的操作

a 写成 x,右移到 q1

q1执行的转移是:y写成y、右移

还是到 q1 状态

q1 读 b

b 写成 y,左移到 q2 状态

q2 读 y

y 写成 y

左移还是到 q2 状态

q2 读 x

x 写成 x

右移到 q0 状态

又回到 q0

这个时候,q0 状态读到 y

执行的转移就到这里

y写成y,右移到 q3 状态

q3,读y

y写成y,右移还是到 q3 状态

q3 现在读的空白符

执行这个转移

空白符还是写成空白符

左移到 q4 状态

这个串读完了

最后停在终态 q4

这个串 aabb 接受了

这个图灵机执行的过程

就是把a和b进行匹配

匹配成功

它就被接受了

如果它不匹配 ,则拒绝

这个例子还告诉我们

图灵机可以接受

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

这个语言不是正则语言

DFA、NFA都不接受

但图灵机可以接受

下推自动机能够做的

图灵机也可以做

再看一个例子

有七个状态表示的一个图灵机

这图灵机接受什么字符串?

我们给 001122 字符串

跟我们刚才的操作类似

开始,在初始状态读 0

执行这个转移

0换成 X,右移,到 q1

q1读 0

0 不变,右移,还是到 q1

q1 读 1

1 换成 Y,右移到 q2

q2 读1,1不变,右移到 q2

q2 读 2

2 换成 Z,左移到 q3 状态

q3 读 1

1不变,左移 q3

q3,现在读 Y

Y不变,左移,还是 q3

q3 读 0

0不变,左移,到 q3

q3,现在读 X

X 不变

现在右移,到 q0 状态

我们进行了一轮操作

现在回到 q0

q0 读的是 0

0 换成 X,到 q1 状态

q1,接下来读 Y

Y 不变,右移到 q1

q1,读 1

1 换成 Y,右移,到 q2

q2 读 Z

Z 不变,右移,还是 q2

q2,读 2

2 换成 Z

左移到 q3

q3,读Z

Z不变,左移到 q3

q3,1不变,左移到 q3

q3,Y不变

左移,还是 q3

q3,读的是X

X 不变

右移到 q0

第二轮回到了q0

q0,读的是 Y

执行状态转移是

Y 不变,右移到 q4

q4,再读 Y

Y不变,右移,q4

q4,现在读的 Z

Z不变,右移到 q5

q5,读 Z

Z不变,右移,还是q5

q5,读空白符

空白符不变,右移到 q6

这串读完了

最后落在终态

因此,串 001122 就被接受

这两个例子,它们有相同的地方

也有不同的地方

这接受的字符串

比那个例子的字符串要多一部分

就是后面这一部分

可以验证

这个图灵机它接受的语言

是 {0的n次方 1的n次方 2的n次方}

这个语言,大家很清楚

我们用泵引理证明了

这个语言是非上下无关语言

用下推自动机是表示不出来的

但是,用图灵机它可以接受它

说明图灵机

比下推自动机的表现能力强

这个图灵机,它的整个模型

写出来

七元组,它的状态、输入字母、带符号

状态转移,由这个状态转移图给出来的

空白符、终态

可以用状态转移函数

表示这个图灵机

还可以用状态转移图来表示这个图灵机

之前介绍有限自动机

还有一种表示形式

就是状态转移表

刚才这个图灵机

也可以用状态转移表

这个状态转移表

第一列是状态

第一行是带符号

对一个状态、一个带符号

有一个转移

像 q0 输入 0

0 转成 X

右移到 q1 状态

有的没有转移

因为这是部分转移函数

q0 输入 1 的时候,它没有转移

没有转移,这里就记“一”

这状态转移表

对应了这个状态转移图

它们是一一对应的

有了状态转移表

可以写出状态转移图

反过来也成立

它与状态转移函数也是一一对应的

说明图灵机的表现形式

可以是状态转移函数

可以是状态转移图

也可以是状态转移表

这一节,我们介绍了图灵机的

形式化定义

图灵机

识别字符串的功能

这节内容介绍完毕

谢谢大家

软件理论基础课程列表:

第一章 基础知识

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

也许你还感兴趣的课程:

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