当前课程知识点:软件理论基础 >  第十三章 图灵机的扩展 >  13.5 图灵机与其他自动机 >  Video

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

Video在线视频

下一节:Video

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

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

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

现在介绍第五节

图灵机与其它自动机的关系

上一章

介绍图灵机时,我们讲过

图灵机具有前面介绍的

有限自动机、下推自动机的一些功能

能够接受之前一些自动机描述的语言

那它们之间的关系是怎样呢?

首先,看看下推自动机

下推自动机有一个栈

现在假如增加一些栈

叫作多个栈的下推自动机

多个栈的下推自动机

定义跟一个栈的下推自动机

是类似的

状态、输入字母、栈符号

以及栈底符号,等等

区别在哪呢?

主要在状态转移

有 k 个栈的下推自动机

状态转移还是非确定的

在 q,输入字母 a

栈顶符号分别为 X1、X2、...、Xk

转移之后,可能有多个转移的结果

其中包括栈顶X1变为一个串γ1

X2变为一个串γ2,等等,Xk

可能变为一个串γk

然后到新的状态 p

这是其中某一个转移

下面看三个栈的下推自动机

多栈机可以用多带机模拟

三个栈的下推自动机

可以用四个带的图灵机模拟

上一节讲过

半无限带图灵机

可以把半无限带图灵机

来顶替它的栈

可以用四个带的图灵机

其中一个带表示输入串

另外三个带模拟它的栈

这样就可以用多带图灵机

模拟多栈的下推自动机

多个栈的下推自动机接受的语言

图灵机一定能接受它

反过来,图灵机用一个栈的下推自动机

是不行的

上一讲讲过

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

这个语言图灵机可以接受

但一个栈的下推自动机

是不能接受的

如果增加一个栈

两个栈的下推自动机

就可以模拟标准图灵机

这是标准图灵机

这是两个栈的下推自动机

下推自动机有一个特点

状态读字符

写字符的时候

只能在栈顶上操作

不能在栈的中间操作

而图灵机能够在符号的

任何一个位置读、写

这是图灵机跟

下推自动机不一样的

一个栈要模拟图灵机是做不到的

但是,两个栈就可以

要读 Xi

把 Xi 这边的符号放在这个栈里

这边的符号放到这个栈里

如果要到某一个带符号位置

图灵机可以移动

一个栈做不到

两个栈中

或者这个栈符号倒这里

或者是这个栈符号倒这里

可以倒栈里任何一个符号了

按这操作

两个栈的下推自动机

就可以模拟图灵机

设计一个双栈的下推自动机

接受 {0的n次方 1的n次方 2的n次方}

这个语言,我们曾经用泵引理

证明过一个栈的下推自动机是不能接受的

两个栈就可以接受

作为大家课后的作业

再介绍计数器机

计数器机是一种特殊的下推自动机

它也有栈

只是计数器栈只有两种符号

一个是 Z0,栈底符号

另外是 X

Z0,栈底符号改变

只可能替换为X^i Z0

X 可以替换成 X 的 i 次方

如果栈为 Z0,相当于数是 0

如果栈里有 X

表示这是非 0 的

X 的 i 次方,表示 i

计数器加 1,表示压入了一个X

如果弹出一个 X

表示计数器减 1

栈底符号弹出

就不能再操作了

就是 0 不能再减 1

计数器机

是一个特殊的下推自动机

接受的语言

下推自动机

包括多栈的下推自动机

接受的语言是图灵机语言

也是递归可枚举语言

计数器机,有多个计数器的计数器机

接受的语言

也是递归可枚举语言

反过来,递归可枚举语言

图灵机语言

是不是能够被计算器机接受呢?

从前面的讨论

具有一个计数器的计数器是不够接受

递归可枚举语言

关于计数器机,有下面的结论

具有一个计数器的计数器机

接受语言的能力

相当于DPDA 语言的能力

两个或两个以上的

计数器的计数器机

接受的语言就是图灵机的语言

它的能力相当于图灵机

证明分两步

第一步:任何一个递归可枚举语言

可以由三个计数器的计数器机接受

第二步:任何三个计数器的计数器机

可以用一个具有两个计数器的

计数器机来模拟

这说明,任何一个图灵机

可以用两个计数器的计数器机模拟

图灵机

与计数器机有这样的关系

那图灵机与计算机有什么关系呢?

首先,普通的计算机能模拟图灵机

对计算机采用适当的数据结构

图灵机的状态、转移,等等

都可以模拟

现在计算机

跟图灵机比,有一个问题

图灵机有一个带

带两端无限的

它可以存储无穷个符号

计算机

虽然存储功能不断地改进

从原来的多少M,现在到多少G

包括将来还可以进行扩展

但所有这些毕竟是有限的

可以通过下面的方法改进

可以在处理器

需要多少资源

可以外挂一些存储设备

外挂,要多少挂多少

计算机完全可以模拟图灵机

反过来,图灵机

是不是可以模拟现在的计算机呢?

用多带的图灵机模拟

多带图灵机,一些带储存指令

一些带储存字符

一些带储存地址

一些带储存所需要的功能

都可以储存在这些带里

现在计算机增、删、改、查这些功能

在图灵机

可以增加一些带

完成这些功能

这说明,图灵机跟计算机的

功能完全相同

这一章介绍了图灵机的功能

可以做一些扩展

扩展之后得到的图灵机的功能

跟标准图灵机完全一样

又介绍了图灵机与多栈机、计数器机、计算机

它们之间的关系

这一章内容介绍完毕

谢谢大家

软件理论基础课程列表:

第一章 基础知识

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

也许你还感兴趣的课程:

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