当前课程知识点:软件理论基础 >  第二章 确定有限自动机 >  2.1 确定有限自动机的概念 >  Video

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

Video在线视频

下一节:Video

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

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

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

我是清华大学软件学院教师罗贵明

今天讲授的内容是确定有限自动机

内容包括确定有限自动机的概念

确定有限自动机的定义

扩展状态转移函数

正则语言

最后介绍确定有限自动机的构造

首先我们介绍确定有限自动机

自动机是软件的模型

它在电子 信息 生物 医学材料等领域

有着广泛的应用

那什么是一个自动机呢

自动机

它就是一个规则

它输入一个字符串

通过自动机的处理

最后输出字符串

如果输出的字符串是接受或者拒绝

我们把这样的自动机叫做有限自动机

自动机的状态转移图

是我们前面讲的标签的图

这个图的结点就是我们自动机的状态

用一个圈的表示是拒绝状态

用两个圈的是表示接受状态

另外在自动机的边上面标记有符号

这个符号就是我们的输入字母

通过输入字母自动机可以从一个状态

到另外一个状态 有一个转移

这个转移我们也叫变迁

在这个自动机里面

有一个状态

它没有前驱状态

只有一个箭头指向它

这一个状态就叫做自动机的初始状态

另外在这个自动机里面

有两个圈的这个状态

也叫结束状态 也叫终态

它输出的是结束

在一个自动机里面

终态可以有多个 也可以没有

所以它是自动机里面的一个集合

状态的集合

在自动机 一个圈输出的是拒绝

自动机在开始处的位置是在初态

当我们导入一个字符a的时候

它就按自动机转移 就转移到q1

再输一个b的时候

它转移到另外一个状态q2

q2在我们这里是接受状态

但是这个串没做完

还要继续输入字符a 它就转移到q3

再输入字符a的时候 它就转移到q4

这个时候这个串输入完了

它落在自动机的一个接受状态

输出的就是接受

这个输出串是aaba

同样这个自动机首先处在初始状态q0

当我们输入字符a的时候

它就转到q1

再输入字符a的时候

这个时候它就转移到状态q5

再输入b的时候

这个时候我们在q5这个地方

它有一个q5到自身的一个转移

我们也叫自环

输入b它自己还是到q5

再输入a的时候 它还是到q5

这个时候串输入完了

之后输出的结果是拒绝

下面再看另外一个自动机模型

这是由四个状态构成的

一个自动机状态转移图

输入串是101001

同样 这个自动机首先处在初始状态q0

当输入字符1的时候 它就转移到q1

再输入0的时候 它转移到q3

再输入1的时候 转到q2

输入0的时候 转到q0

再输入0的时候 它回到q2

再输入1的时候 就转到终态q3

串输入完了

落在一个结束状态

属于输出的是一个结束

11010

同样这个自动机首先我们处在初态

当输入1的时候 它就转移到q1

再输入1的时候 它回到状态q0

当输入0的时候 它转到状态q2

再输入1的时候 就到了状态q3

再输入0的时候

它就转到状态q1

这个时候我们看串都完了

落在一个非接受状态

所以输出的结果是拒绝

通过前面几个例子

我们看自动机它有哪些特征

我们怎样去给确定有限自动机

它一个形式化定义

这是我们下一讲要介绍的内容

这节内容讲到这里

谢谢大家

软件理论基础课程列表:

第一章 基础知识

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

也许你还感兴趣的课程:

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