当前课程知识点:软件理论基础 >  第九章 下推自动机 >  9.1 PDA介绍 >  Video

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

Video在线视频

Video

下一节:Video

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

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

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

我是清华大学教师罗贵明

今天我们讲述的内容是下推自动机

内容包括下推自动机 也是PDA 它的介绍

下推自动机的定义

下推自动机的即时描述

下推自动机的语言

最后介绍下推自动机

与上下无关文法的关系

什么是下推自动机呢

之前我们介绍了一类特殊的自动机

叫确定有限自动机

这个自动机描述的语言是正则语言

通过这个正则语言

我们又介绍了另外一类自动机

就是非确定有限自动机

这两个自动机描述语言

都是相同的正则语言

实际上正则语言

还有另外一种描述方法

就是正则表达式

通过这个正则语言

我们还引出了一个文法

就是正则文法

在上一讲里面

我们介绍了上下无关文法

这个文法它描述的语言

是上下无关语言

看这种结构我们跟他比较的话

我们就觉得它们之间

有一种很类似的关系

这个正则语言它有自动机

那我们上下无关语言它的刻划

是不是也有一种自动机

来刻划它的语言呢

如果有的话

这个自动机是什么样的自动机呢

这就是我们要讲的下推自动机

那下推自动机

实际上它是一个非确定有限自动机

加上一个堆栈构成的

我们的自动机用状态机来描述

它有一个输入串 再加上一个堆栈

在这个堆栈里面有一个特殊的符号

叫栈底符号

每一个$里面除成一个符号

实际上这个栈底符号可以是不同的

你像这个是用Z0做栈底符号

这个是用一个$做栈底符号

在堆栈里面要写符号或者要去掉符号

始终是在栈顶上面进行的

我们可以用状态转移

来描述下推自动机的它的整个一个运作

像这里a是表示输入符号

b表示我们栈里面弹出符号

而c是表示栈里面压入符号

也就是在q1这个状态

我们经过了这些运作之后

再转到q2这个状态

有时候我们也可以

把刚才的这个符号记法改成这种记法

下面我们看看它是怎么样去运作的

这是一个栈

栈底符号是Z0

栈里面符号有b、h、e

栈顶符号那就是b

我们现在要给一个输入串

我现在在q1这个地方到a

把栈顶b换成c

你看这个栈就换成这样

最后再到q2这个状态

我也可以栈顶一个符号我们去掉

我导入输入符号a

然后把栈顶b换成空串的话

现在这个栈就变成了h了

这就到了q2这个状态

我也可以在栈里面不动来做转移

在q1这个状态导入a

我认为栈顶是有一个空串

空串还是标空串之后到q2

那我就可以输入a

栈顶ε不变

这里还是保持原来的栈里面的结构

当然这种描述方法

是始终认为我们栈顶上面有一个空串

这个在非确定有限

这个下推自动机里面是可以的

那有时候我们说这种描述

也可以用另外一种描述

就是要保证栈顶是不动的嘛

那我就可以把栈顶这个b我弹出来

然后压入的一个栈符号也是b

也就是我们换成这种表示

这种表示跟这种表示

它的作用是一样的

但是它们的表示形式是不同的

这种表示我们说在以后

我们讲确定的下推自动机里面

使用这种表示

而这种表示可以用在

非确定下推自动机里面

下推自动机里面还允许把栈

也可以弹出来

现在我栈里面只剩下栈顶符号

输入一个a

把栈底Z0也弹出来

这时候栈里面啥符号都没有

然后到q2这个状态

那如果栈里面

什么符号都没有的时候也是空栈

我们再进行操作的时候

你比如说我这q1这个状态我读a

把b换成c到q2

那这个时候发现这个

没有这个栈里面符号b

这个自动机的在q1这个地方

它就停止就拒绝这个输入

这个栈里面是没有这个符号b

那如果我把这个栈里面我认为有个空串

把空串写一个c 这是不是可以呢

也是不可以的

这个时候它也是在q1这个状态也停机了

也就是在q1这个状态

这是空串的时候

你到任何一个符号改写的话

这个都是不允许

它都是停机的

也就是说我们在下推自动机里面

栈底符号是非常重要的

如果栈里面没有栈底符号或者没有符号

那你做任何操作都是拒绝的

当然这种操作我们说是可以的

也就是原来是Z0是栈底符号

我换成另外一个符号b 然后到q2

这个操作是可以的

这个时候新的栈底符号就是b了

这个状态转移里面

刚才讲了a是输入符号

b是栈里面弹出来的符号

而这个w压入的符号可以是一个串

我们开始是讲了一个符号

这个可以压入一个串

把它写成状态转移函数

那就是原来我们有的是状态q1

要输入的符号是a

原来的栈顶符号是b

这是最开始的状态

那经过我们这样的转移

把b弹出来 换入一个新的串的时候

我们到q2这个状态

这个时候我们就可以写成为

这个状态q2

这个时候 栈把b就换成了一个串w

注意我们这里用一个大括号表示的

这就说明我们这个状态转移可以是多个

也就是说是一个非确定的情况

下面我们看这个例子

这个是我们栈里面

我们输入一个串

假如我们输入a把栈顶b换一个串cdf

那这个时候我读入这个a

那cdf是不是把这个b

你们改成cdf呢

我们说是不行的

因为我们栈里面

每一个这个单元格只放一个符号

那这个时候我们把b换成cdf

这个换法就是我们读

这个串是从左到右cdf

那我们压入这个栈的时候

我们就是从上到下压

那就得到这样一个串了

这个b就换成cdf

每一个单元格里面我们是放一个符号

对于我们下推自动机

我们刚才讲了

我们这是非确定的

也就是对一个状态q1

同样的输入

同样的栈顶符号

如果把这个栈顶b换成c

它可以转移到q2 这是一个转移

如果把b换成d

它可以转移到另外一个状态q3

这个是允许的

而且在我们这个转移

里面我们的输入可以是空串

也就是可以允许ε转移

这就是我们强调我们的下推自动机

现在介绍下推自动机是一个非确定的

那在一般的情况

我们在q1这个状态读入a

栈顶b可以把它改写成一个符号

也可以改写成一个串

那一般情况下

你比如b换成一个串w到q2

b换成一个串又到q3

我们把这样的状态转移

用刚才定义的状态转移函数q1

输入a 栈顶是b

就换成像这样的转移就有两种转移

一个是q2是把栈顶b换成w的

另外一个是把b换成u到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笔记与讨论

也许你还感兴趣的课程:

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