[音乐] 嗨，欢迎回来。
接下来呢我们来介绍有限状态机。
那么有限状态机这种机器呢，它是源于说
我们对于这个语言的字符串的这个识别的这个需要， 也就是说我们会面临这样的一个问题。
当我给定一个字符串， 我需要判定呢是否是属于
给定的一个语法G，它所产生的这个语言L(G)的。
也就是说我要判断一个字符串是不是属于这个集合， 这么一个判定。
那么一般来说呢，这是一个非常 这是一个难解的问题，并不是有一个确定的一个过程。
实际上呢它涉及到我们上一节所讲到的语法分析的问题，
就是给你一个句子，如果这个句子是语言当中的句子的话，那么你要给出
它的一个构造的过程。
跟我们在形式系统当中进行证明
这是一样的，也就是说你，假设说这个命题是正确的，那你要给我一个公式的序列，
给出一个证明，说明它是正确的。
那么你，如果判定说这个句子是属于这个语言的， 你就也必须要给我一个过程，就是一个构造的过程。
如何用这个产生式一步一步地推出来， 这就叫一个识别和判定的一个过程。
那么一般来讲，对于乔姆斯基的这个 各种类型的这个语法来说，这是一个难解的问题。
但是呢有个好消息，就是对于一个，对于我们三型语言，或者三型文法来说，
也就是正则文法和正则语言来说，它是可以通过一个 比较简单的这个识别机器来进行判定的。
那么下面的这些图里边呢，就是这个机器的大概的样子。
那么它中间呢会有一个机构，这就是机器啦，然后机构当中存在很多的状态。
然后呢左边呢会有一系列的这个字符的输入，就是说你需要判定的字符串，
一个一个地按照字符挨个地输到这个机器里来。
那么机器呢通过一阵轰轰呢，轰鸣啊，那么最后呢，当你
最后一个字符输进去完了以后，它会给你一个YES or NO的这个回答，如果是YES，
那么就说明你这个句子被接纳了，这个句子呢符合这个语言的 文法，它是这个语言的句子。
如果是NO，那就很不幸地是，你这个字符串呢被拒绝了。
那么相对于我们说一个机器啊，大家肯定
马上脑海里头想象的都是这种带齿轮，或者有很多电路板
通上电，加上汽油，轰鸣的这些东西。
叫做机器，而实际上呢，我们 通常所说的，按照广义上所说的machine来说，
我们知道有个，英语有个单词叫mechanism， 就是机制的意思，是一种
什么什么什么形成的机制，那么也就是说它实际上是代表一种规则。
那么machine呢和mechanism是同源的，它显然是同源的单词。
所以呢，对于机器来讲，它也，其实也就是一个，广义来讲，是一个系统。
它呢会接受一些输入，然后呢它会改变自身的状态。
然后最终呢会产生一些输出，那么这种都叫做 机器。
所以简单来说，只要是按照规则来运行
不是那种喜怒无常，任意变化的这种系统，那么我们都可以叫做一个机器，它的行为是可以- 预测的。
它是可以由一些规则来表达的，那么这种都叫做机器。
那么这里头的所谓的状态呢， 就是指这个为了完成这个机器的任务，
而对我们的这个序列进行一种临时的归类，每一个状态都是一种临时的归类。
那么这是从归类的角度上来理解。
当然你也可以从这个 记忆的角度上来理解。
说我读进了一个字符以后， 我就产生了一个记忆，我记住了。
那么下一次呢再 读入一个别的字符的话，那我应该做一个什么样的一个归类？
那么所以呢，这可以理解为对于一种记忆的一种模拟这种状态。
那么在逐个地接受这个字符输入的过程当中， 字符呢从左到右进行扫描，一个一个字符进入这个机器，
那么这个机器状态呢每进一个字符，它就，状态就改变一次。
那么这样呢，整个的过程当中，这个状态呢会改变很多次。
那么最终呢当你这个字符输入完成，最后一个字符进去以后，
那么这个机器呢最后一次状态的变化会停在某一个状态。
然后呢会有产生输出。
那么对于有限状态机来说， 那么就是它对所有的输入，这个机器的
状态、 数目都是有限的，它不会再有更多的状态产生。
那么这种呢就叫做有限的状态机，有限状态机。
叫做Finite State Machine，简称呢叫做FSM。
那么我们从严格的定义上来讲，一个 有限状态机呢它就是一个五元组，它包含了五个元素，
A,S,Y,s0和F，我们下来看看每一个元素都是指什么。
A呢是指这个输入字符的一个字母表，也就是字符集了。
如果相对于这个文法来说，它就应该是最终的字符集的那个
终结符的那一部分，就是属于终结符集，所以它是 输入字符上的子母表。
S呢就是机器的所有状态的 集合，那么尤其对于FSM来说，它是一个有限状态集，
所以这个S呢是一个有限的集合。
然后当中的Y呢是S的一个子集， 因为某一些状态呢被称作为接受状态，
就是标注为Y的那个状态，就是说当你机器
停在这个状态的时候，就说明这个字符呢被接受了，这个字符串。
然后最终呢，最后呢，还有一个s0,s0呢是 在s当中的一个状态，其中的某一个状态，我们称作为初始状态。
那么机器呢，开始工作的时候，都是从s0开始工作的， 从s0这个状态开始转换，读入一个字符，它变成
一个下一个状态，下一个状态呢再读入字符，再到下下个状态。
所以最初的那个状态，叫做初始状态s0。
然后最重要的是这么一个状态转移函数，
F，它是SxA到S的一个函数，也就是说它是一个二元
在二元的函数，它呢接受 在某一个状态，就是S，第一个参数S下，接受
一个输入字符，就是第二个参数A，所引起的状态的变迁。
那么最终它会变到一个，下一个状态，这就叫状态转移。
那么它是一个函数呢，所以它是一个状态转移函数。
那么这样的有限状态机就是由这么一个五元组来构成的。
我们来看看一个例子，那么这个A呢是a,b，
那么所有的字符串呢只包含a,b两个字符，S呢是s0,s1,s2，它有三个状态。
那么Y呢接受状态，是有s0,s1,就是有两个状态是接受的。
那么其中呢s0是一个初始状态，
那么我们这个状态转移函数我们单独列了一个表来进行表示。
我们来看看这个表是如何理解的啊。
那么它每一行呢是一个状态， 有一个状态的对应，每一列呢就是当这个状态读入字符的时候会发生什么样的转变。
那么中间的这个数值就说明是目标状态转移到什么状态，比如说我们说 在s0的情况下，读入一个字符a,
它还在s0，也就是说它状态没有改变， 但是如果s0的状态下读入一个b，那么它就会把状态呢变成了s1。
那么再看一个例子，s2的状态下， 它读入一个b，还在s2待着，
读入一个a，它也在s2待着，也就是说在s2这个状态下呢，
它就变成了一个类似于陷阱的一个东西，一个陷阱的一个状态。
在s2这个状态下，不管是读入a或者b， 那么它都还是停留在s2，所以呢这个机器呢
就会在s2这个状态里边，就陷入进去，它再也 不能够离开这个状态了。
那么这个呢就是 对于状态转移函数的解释的方法。
陈斌副教授
