离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。 本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
90-状态图
Loading...
来自 Peking University 的课程
离散数学概论 Discrete Mathematics Generality
155 个评分
从本节课中
形式语言与自动机：有限状态机
与讲师见面
陈斌副教授
北京大学
[音乐] 嗨，欢迎回来。
前面呢我们看到这个 有限状态机它主要呢是由状态转移函数
来进行表达的，那么我们在分析和 读取这个状态转移函数这张表以后，我们发现呢
它确实不太容易去理解，尤其是状态进行转移的时候，
那么它是如何转移，转移的路径是什么呀，等等。
那么所以呢，我们肯定会有别的办法，去把这个过程更加的这个
形象化， 那么我们又要说那句俗话了，叫做一图胜千言，
那么一张图呢胜过一千个这种状态转移函数的表格，所以我们下来
就用状态图来表示一下这个状态转移函数以及有限状态机。
那么这个状态图呢，它是一个有向图，首先是， 而且呢是边，它的这个边，带标记的有向图，
那么这样呢我们就想想，它是一个，应该确切的来说是一个赋权图，是吧。
那么这个有向图里头，这个节点呢，就是状态。
因为是状态之间的转移，所以呢由一个节点， 然后以连接边，然后呢再到下一个状态，下一个节点，
那么状态转移函数就决定了这个边的走向，以及在边上的标记。
那么边上的这个标记呢，就代表说，由一个状态，
读入一个字符，然后转移到下一个状态，那么这样呢就是状态转移函数的内容。
那么我们呢，特别地，把这个接受状态，因为其中这个Y这个子集，
就用两个圈来表示，当中普通的节点是一个圈，那么用双圈来表示接受状态。
那么边的具体的定义是说， 如果这个状态转移函数把sj，这个
状态，然后在读入a的情况下，转移到sk的话， 那么我们就从节点sj做一个有向边，
这个边呢做一个标记a，然后边呢到达目的地，
是这个sk，起点是sj，终点 是sk，然后呢这个边的标记，标记为a，
这样的一个边的定义，我们呢把这个初始状态s0做一个特殊的一个标记，
就是用一个单独的一个箭头把它指出来，就所谓的无源箭头也就是说它
没有来源节点，就是它其实就只是一个标记而已，就标识
说这个机器启动呢，都要从这个s0这个状态出发。
好了我们看看这个例子，这个实际上呢整个的看起来就是一个赋权的有向图，
那么对于这个边它有赋权，是吧，它边呢，标识了这个a呀，b呀，
a，b这样子的读入字符，这样的一个赋权。
那么对于节点它也有赋权，最起码的赋权呢是 说这个节点是接受状态还是
拒绝状态，是吧，接受状态，双圈，那么实际上是，也是 节点的一种属性，也是赋了权的了，那么所以我们看这个
这是一个状态图，我们就可以看到，从s0读入b，然后到s1，
s1读入a，还回到s0，这个就是我们上一节所看到的这个状态转移函数的样子。
那么具体的这个解释呢，我们到下面来看看。
那么现在我们来讨论这个机器它所识别的语言，
这一个机器M，它所识别的A上的所有的字符串， 是怎么定义呢？怎么样才叫做识别这个语言？
那么就是说它把它所有能够识别的所有的字符串都放在一起，这就叫它识别的语言。
那么怎么叫识别？就是说一个 字符串w，它是A*的一个成员，
A*，A是我们的这个输入字符，字符集，所以A*呢就是包含了所有
可能组合的所有的字符串，我们这个w这个字符串长度为m，所以呢它的
这个构成就是a1，a2，一直到am，那么这个从左到右，这么一个字符串。
那么字符串呢，从a1开始，逐个地把它输入到机器里头
去，a1的时候，那么就是从s0开始，那么a1呢 s0，a1，会转到其他的一个状态，然后其他状态
呢再读入a2，再转到下一个状态，再读入a3，再转到下一个状态，
所以呢从s0开始，就有s0，s1，s2，一直sm， 就是m加1的这么一个状态，它确定了一个状态的序列，
最后呢在读入am之后，它会停在sm这个状态，所以它确定了一个状态序列。
那么这个序列呢它是有约束的，就是说
si-1读入a它会转移到si，
这么一个约束，也就是说我们按照这个图论上的这个术语来说，
它确定了一条拟路径，这条拟路径呢是从s0这个节点出发，
然后a1这条边，再到s1这个节点，a2这条边，再s2这个节点，
a3这条边，然后一直到am这个边，到sm这个节点
终止，这就是一条拟路径，就是节点，边，节点，边，这是一条拟路径。
这个我们用图论的术语，非常的清晰。
那么最终，如果说这个sm，它是Y这个接受状态集合当中的一个成员的话，
那么我们就称作这个m，就识别，这个机器就识别了w这个字符串， 叫做识别，或者叫接受。
所以呢我们来看看这个状态图，既然我们把这个FSM，就有限状态机变成了图了，
图更容易理解，是吧，我们就变成了 做这个拟路径，就是做这个拟路径，我们来看看我们前面这个例子，
状态图它识别什么样的语言。
我们来看三个例子， 第一呢，ababba，我们从s0开始，
读入a，就还到s0，然后读入b，就到s1了， 再读入a，还回到s0，然后再b，就是s1，
再到b，就跑到s2，再到a，还到这个s2，
最终呢，输入停止，那么状态停在s2，它不接受，所以呢它不识别这个
ababba，第二个，baab，
那么从s0开始，读入b就到s1了，那读入a呢，又回到s0，
然后再a，还在s0，再到b，s1，最终呢停在s1上，
那么既然停在s1上，s1呢是一个接受状态，所以呢，
这个机器接受这个baab，最后一个，空串，
空串呢就是没有任何的输入，那么从s0开始，那么它就停在s0， 所以呢它是被接受的，s0被接受，
当然并不是所有的s0都会被接受，当然不同的这个 状态机，有的可能s0它不是接受状态的，
所以你对于空串进去的话，它就不会被接受。
所以呢这是这三个例子。
那么我们最终要 总结一下说，我们这个例子的机器它是识别什么样一个模式的字符串呢？
因为所谓的正则语言它都有模式嘛，我们经过分析，
只有从s0出发，然后到了，读入一个b，到s1，
那么s0，s1这个相互流转并没有什么关系，它都是属于
接受状态，s2，只有s2是一个 不接受状态，而且呢s2这个状态呢
具有陷阱的性质，一旦进入了s2这个状态你就出不来了。
那么怎么会跑到s2？
那么我们说，从s0开始，读入一个b，到s1，s1呢就有点危险，在悬崖的边缘，
如果在s1状态下你再读入一个b的话，那么它就会 跑到这个陷阱里边去，到s2，就一直被拒绝。
所以我们说，这个状态机
它识别的是不包含连续两个b的字符串， 你如果有连续两个b，那么一个b就到s1，再一个b到s2，
就死了，就停在这个拒绝状态，所以这个呢它的模式是这么给总结出来的。
那么对于正则语言来说，跟有限状态机之间的这种关系，
我们刚才最早的时候已经提到过有限状态机呢就可以用来识别 正则语言，那么它最终的这个精确的这个定义是在
Kleen定理里头被说出来，被提出来，它说字母表A上的这个形式语言L
它是正则语言，当且仅当存在一个有限状态机M， 使得这个L呢等于M所产生的这个语言，
这样呢，这个Kleen定理呢就把 正则语言和有限状态机一一对应到一起了。
那么比如说我们构造一个自动机M， 能够识别呢恰好以两个b结尾的字符串，
那么这个呢，就刚好跟前面的那个 有点相反的意思，前面是一旦碰到连续两个b就被拒绝了，
但这个是结尾，两个b结尾，那么我们也是构造，从s0出发，读入一个b就到s1，
再读入一个b就到s2，s2呢是一个接受状态， 那么如果说这个字符串到这停了，那么它就被接受；
如果后面还有，那就分两种情况，后面如果有a，那么我们
就破坏了连续两个b，就还回到没有b的这个状态，s0状态。
如果是读入是b的话，那么这个b和前面那个b 还是连续两个b，所以它还在s2呆着。
所以呢实际上我们通过这个状态图就很容易构造出一些
这个特殊模式的这种正则语言， 对吧。
那么这样呢，我们可以把对应的正则表达式给它写出来，
就是a或b，然后*，然后最后呢连续两个b，
这么一个，那么这个呢，就把正则表达式，正则文法，和正则语言以及
有限状态机，整个呢就全部都统一在一起了。
