从NFA到DFA转换是什么课程内容

呃，正则的内容就是他为什么这个有这个正则？他是背后的一个原理是啥啊？学术上的一个原理叫做那个自动机。 呃，自动机呢？他听起来很高大上，他实际上就是，呃，我们的一些流转图啊，你可以叫简单理解状态流转图，嗯，比如说这里有一个自动机，我给你放大一点哈， 放大 ctrl 加加来看这个自动机吧。 呃，这里有一个自动机，这啊就是状态流转 图。这个转转头转出是啥含义呢？呃，这个箭头就是入节点，就是你要这个图，你要从哪里开始便利啊？这里每个上面写了一个一二，就是你的一个 步骤吧，也不叫步骤，你不一定是非要只能走一到二。呃，你能走的步骤呢，取决于他后面的这些箭头，你可以跟着这些箭头走，然后假设这里 呃进来的是初始位置，就是在一上哈，然后呢，这里这个每个箭头就是你输入一个 a， 然后他就会导致跳到 二。嗯，再输了一个 a 就会导致跳到一，再输了一个 a， 导致跳到二，再输了一个 a， 导致跳到一。啊，这个就是一个这样这么样的一个状态流转图。好，他的歧视状态就是 是这个箭头，但他也有中指状态，中指状态就是这个圆上有两层的，叫做中指状态，因此呢，这个机器呢？他可以接受的自助串是什么呢？啊？假设你只输了一个 a， 他就跳到了二，对不对？然后他遇到这种双元的，他就，他就，你想停止，你就可以停了他，于是他可以接受 a， 只接受 a。 好，假设你输了一个 aa 会发生啥？ a 跑到了二，再输了一个 a， 又跑到了一，你就不输入了， 此时他的结束位置并不是在双元上，他就拒绝接受啊。就是正则上匹配，就是匹配错误，返回 fast 就是这种状态。这个呢，就叫做，呃，那个自动 机，整个这个自动机就是这样玩的，其实就是状态流转。图 d f a 和 n f a 有奖吗？啊，这个就叫做那个确定性自动机吧，这个是 d f a 吧，然后下面就是非确定性自动机了，就是那个 n f a， 我们现在就叫做确定性自动机。 好，这个可能你看着很简单，那感觉没啥。那我们玩点复杂的，他下面有例子哈。 下面有例子，他是看他这个是搞一个啥例子。来看一下这台机器，这台机器哪些 zoo 串能接受，哪些不能接受？嗯 嗯，他这里也举了个例子，我们看一下这个 a b 是否能结束吧。呃，首先你在这个初始状态就是一了吗？此时他有两条路径啊，如果你输入 a 的话呢，他就不能二，如果你输入 b 的话呢，他还是在一上 啊。所以说输入第一个输入 a 拨到了二，然后又输了，又输了 b， 我们我们要测试 a b 哈， 然后此时在二上输入 b， 那就蹦到三，此时不再输入，他就停止，然后正好在双元上，那就是可接受的，也就是 ab 是可接受的。你再看这个 baba， 默认你就在一上，然后输入 b， 那还是在一上，再输入 b 还是在一上啊？当然他说的是 b a 哈。呃， b 在一上，再输入 a， 跑到二上，再输 b， 到三上，再输 a 啊，回来还是跑到三上啊？所以说这个 bab 也是可接受的啊，再看一下这个 a， 好磨轮，在一上，此时输入一个 a， 好停止输入， 然后他中指状态不在双元上，他就不可接受啊。再看这个 bba 啊， baa， 先输了个 b 在一上啊，又输了个 a 啊，在二上右输入 a， 然后呢又回到二上，此时中指输入，然后这个 b a a， 这个他就不可接受啊，当然巴拉巴拉还有一堆哈。呃，这个呢，就是一个自动机的一个玩法，这个是确定性自动机。呃，不知道 这样大家能不能理解这个，你看这个过程。呃，如果你能掌握这个编程思路，或者说你有这个思路呢？呃，你可以用程序来模拟一个这玩意啊，或者说模拟这么一个状态流展图，然后呢 设计一个状态流转图，然后呢你能去匹配上某些特定的一些支付串啊，这个呢，其实不就是跟正德的一个原理是一样的吗？ 他这里所说的确定性是什么含义呢？嗯，确定性就是，嗯，你每到一个节点，他都有下一个节点的一个， 无论你输入什么，他都可以走向下下一个节点，这就叫确定性。当然这样解释你可能不太理解，我们看了不确定性 你就知道啥是确定性了，这里他有代码实现，我们就不讲了，我们就我们再去看那个非确定性。 好，他这里提了一个问题，假设我们想要一台有线的自动机，他能接受 a 和 b 组成的 第三个字符是 b 的任意字母串。这啥意思？ a 和 b 能组成的第三个字符，也就说你这个字符串只要是和 a 和 b 组成就行，但是你必须是第三个字符串是 b， 比如说，嗯，那个 aab， aabb， bbb， 或者说是 逼逼逼逼逼逼逼啊，只要是第三个字符是逼就行。那你怎么去设计这台机器啊？他这里给设计了一台，呃，我们可以试一下哈，我们就拿这个 a、 b、 b 来试一下，在我们默认在一上，然后我们输入这个 a， 然后蹦到了二上，我们再输入 b， 蹦到了三上，我们再输入 b、 a、 b、 b 嘛， 然后蹦到了这里，蹦到了这个正好这是中指的位置，然后此时当然你可以还继续输入，你只能输入 a 和 b 吗？ 你无论输入什么，他都是在这个五上，他就出不去了，这样他就设置了一个呃确定性的自动机，但是呢，他 他他又他又在问，刚才是接受倒数第三个字符哈，那我们倒数第五个字符怎么办？倒数第 n 个字符怎么办？呃，就是你， 呃，就是你无法确定这个，呃，在结束之前他这个支付串到底有多长，此时怎么办？他那个就提出了一些挑战。呃，你当然你可以设计只说，只不过说这个增动机呢。呃， 你不是你不说三吗？那我就反正我就走三步，然后就让他转呗，你输啥我都让他在这转。你不说倒数第五个吗？那我前面我就拼拼五个，那我就拼完以后在这转呗。那其实也可以，赢上也可以，但只是说 说他画的画这种状态图就比较麻烦，因此呢他就呃设计了另外一种这个自动机，只是说他这个这个规则稍微变了一下，然后呢？让他能实现上面的工作，而且画起来简单一点。 我们来看一下这个是，呃，咋实现的？看一下啊？ 呃，对对，每一个输入序列不再只有一条执行路径处于状态一，并且读入 b 的时候，他可以按照一条规则仍然保持状态一，也就说，呃， 这个路径上是你处于一的时候呢？以前是，呃左边是 a， 右边是 b， 逼就明确的他就是一分为二啊。现在呢，他是可能应该是，就是你说的有两个逼，就是这个可以在同一条路径上，就是同一个逼可以出现在两条路径上。那因此呢，你可以有选择的走走一，也可以有选择的走二。 我们来看一下这个，嗯， b a a 是否接受？呃，假设呃开始状态就是一嘛。嗯，然后你输入 b， 那你可以是走这个 走一，回来也可以走到二，然后我们我们假设哈，这两种状态我们属于量子状态，我们都走了，然后我们再输入 a， 然后呢，你第一条分叉是我们回到了一，然后你如果是在二上呢？我们是去了三， 好，我我，我们现在是亮的状态哈，同时在一和三上，我们再输入 a， 呃，我们，我们在这个上面，我们也可以在一上呢，我们又回到了一，呃，我们在三上呢，到了四。那此时呢，有一个分支是到达了一个终点，那我们就认为这个是可接受的。 呃，如果是你在这种量子状态上呢，是没有到达一个终点，那我们就认为你是不可接受的 啊，应该是只有这一个区别，应该是只有这一个区别。我理解是我之前，我之前看我也，我忘了，差不多了。嗯？ 为什么我，我不太在乎这个哈，因为下面他说了，呃，非确定性的这个有线自动机呢？他是可以转化成确定 性的有线自动机，无论是什么样的自动机，他都可以这么转化。转化的原理是什么呢？原理就是你可以对 这种非确认性的有线自动机呢，这种量子状态呢？我们可以做一个路径便利啊，我们把路径便利完以后呢，他自然他就转化成一个确定性的一个自动机了。 怎么把 af 转成啊？转的方式，刚才我们其实已经模拟了我们去执行它的过程，其实就是把它转成这个 dfa 的过程。 嗯，最简单方式，你就是做一个路径便利。嗯，当你不确定，嗯他是否接受的时候。比如说刚才我们输了这个 a， 我们输了这个 a， 我们不确定。嗯，这个 个下一步啊，我们出 b 的时候，我，我刚才说了 b， 我们不确定下一步是留在 a 上还是走，在走，在这个留在一上还是走。呃，走到二上去。 那我们保持两个节点，我们同时在，就两条分支，我们同时在。然后呢，我们继续去接收下来下面的支付串啊，直到有一个分支触达了这个终止节点， 此时你实际上已经是便利了两条分支，而且两条分支都便利完了。呃，你把刚才便利的路径展开，不就是上面的这个确定性的这个自动机吗？ 不是模糊搜索，是精确搜索，你优化以后可以做模糊搜索。 那现在呢？这个确定性和非确定性的这个自动机呢？我们概念其实已经知道了，然后接下来呢，他给了一些代码实现，然后，呃，当然这本书呢，他讲这些东西的目的呢，也并非是 讲这个自动机本身，他这本书呢是讲机器， 他刚才给了两种不同的机器实现，然后呢在这种机器实现呢？呃，他认为基于这种机器呢，我们可以实现正的表达式，当然你不基于这种机器依然可以实现正的表达式。 好，这本书呢，他马上呢就去问了另外一个问题，就是说刚才的这种自动机呢，他能不能处理 这种括号的问题？能不能处理这种括号的问题？呃， 我，我告诉你答案哈。呃，啊，对，这本书就是编程的本质，我，我在那个我推了好几次了，他能不能处理这括号的问题啊？他实际上是不能处理括号的问题。我们在做趴测的问题的时候呢， 他本身就有一个括号的问题。呃，如果他没有欠套，还好我们说过他真的表达是里面的括号是可以欠套的，如果有括号怎么办？ 嗯这本书给出来的答案呢当然是我们加一个站就够了，就是我们口号下压一下加个站，这个我们背过算法的应该都知道，所以说你要在实现这个程序的解析器 的这个括号的这个地方呢，你也要记得。呃，如果实在是抓耳挠腮搞不出来，你就想一下啊，是不是可以加一个外置存储器啊？加一，比如说加一个站，甚至你加一个数组也可以实现。好，嗯，我们再回到这本书， 嗯，当然这本书的这个目的呢，他也不也不仅一次，他认为。嗯，这个有没有能比这个 呃下推自动机，下推自动就是带站的那种自动机更加强大的机器呢？ 因为刚才上面两种都是机器，然后他就提出了一个叫终极机器。啊，就是，呃，图灵机啊，当然他讲完这个图灵机以后呢，他还讲了另外一 些机器，比如说 number， 演算，然后还讲了不可能的程序。 嗯，那个反正越到后面越好玩。嗯，所以大建议大家来看一下这本书啊，当然这本书的内容已经脱离了我们今天的主题，嗯，我们今天的主题是那个正则表达式的一个实现原理。 好，应该我们这节课就完事了。 好，大家可以简单的问问几个问题，我们就可以睡觉了。 录了没有啊？录了，谢谢谢谢赞。 这个是另外一本书， really 用的这个主播用的这个 o b s。 这个这个 o b s。 一个应该是一个开源软件， 大家有啥问题，然后要没啥问题就就就早点睡觉。 哦，感谢关注感谢关注啊，那个没有关注的，大家可以可以关注一下。桌面。是啊，桌面，你说的桌面，这个很古老了，这个桌面 你看一下。这是能，这是看桌面的地方吗？这也不是这个桌面，是那个吴邦图的那个桌面。吴邦图十六，你听过没有？ 那个桌面我也不知道叫啥桌面。嗯，反正是很老了， 但是他这个系统呢是 wobble 二十二十二，只是说现在因为有很多软件 他在这个最新的桌面上，他不支持，然后我就装回了这个桌面，而且他那个你看这是在闪，这是 bug。 嗯，这种 bug 呢，我用了好多年了，我能，我可控，我知道他有哪些 bug， 也知道怎么解决。呃， 但是新的桌面呢？它有很多 bug， 它不可控，我也不知道怎么解决，因此我也不喜欢那个新的桌面。啊。对，这个可能是是这种桌面吧，看这种 bug 一直在闪。这提示你这个保护眼睛。 呃， arch， 我以前是装的 arch， 然后后来滚挂了，然后时间长了就不想再装了。就就是每次你急用的时候就会挂这个不太稳定。 这个吴邦图还是我就不更新，反正就很稳定。呃，有有一有一台机器已经装了，从吴邦头出来到现在有十年了吧。快了快十年了，一直在那个电脑上运行，他都就不升级 cy。 反正到现在一直很稳定，都不出问题。 好，大家。呃，没啥问题啊，无帮图更点，更新必崩溃。那就不更新，少更新，尽量不更新啊。欢迎这个网言沉迷已经已经来晚了，已经讲完了，可以关注我一下，然后我把这个视频 剪出来，剪出来稍微剪一下，然后发到 b 站上。 好，大家没啥问题，我们就就睡觉了，睡觉了。这个正则暂时讲完了， 其实就相当于讲了一个小型的一个边缘里，这个边缘里相对简单一点，如果你 输入法是搜狗输入法啊，如果你是那个那个 啊，如果你自己没有实操过，你建议实操一下，你实操一下呢，基本上相当于会写一个基础的一个 编，编译要绘写一个编基础的编程语言了，只不过这个编程语言呢，很多算字，我们姑写叫他算字。这些小的节点具体怎么实现呢？他是不一样的，比如说你要实现一个函数，实现变量，还实现其他的东西。 请你复用现在的这一套框也不叫框架吧，这种格式结构构造方式，你复用这些东西呢，依然也可以实现一个编程语言。嗯， 也是这一套。然后趴色的话呢，这个就是非常简单的趴色啊，如果是复杂一点的趴色，肯定不是这样，写就要写成留的方式，嗯，就要复，类似于复用他复用这几个接口吧， 那个辣死 nice 的晕染回顾，然后服用这几个接口，在一个流上上下操作，而且是在地规的过程中去操作， 嗯，才能去好的做一个好的一个 pass。 当然这个编程语言写的最麻烦的地方就是 pass 这一部分， 嗯，而一旦 pass 完以后，拿到这个 ait， 在 ait 上实现每每个节点的一个具体的一个内容的时候呢，他反而会变得简单起来。嗯，所以说那个市面上有很多那个书， 就科班学那些书，什么龙书虎书，他们很多都会把这个最难的部分当成最精华的部分，就是 past 的那部分，然后去学。很多人也是这样，上课上过来的， 其实是没有学到精华的。精华在后面，精华在这些每个的具体实线上， 每个功能的具体实现上，比如说函数怎么实现？作用欲怎么实现？嗯，变量怎么实现？放循环怎么实现？地规怎么实现？ b a 器后端简单还是前端简单？应该是后端吧，前端。前端你你也得看， 反正 passer 不简单，反正越过了 passer 的，其他的还行。 嗯，边气你。有的时候你，你做的时候，因为你要把你要既要兼容你上面一层，又要兼容你下面一层，上面一层就是一些语法不能变，还你下面一层，就是可能硬件也换了目边边与目边也换了 你，你只只能在中间去做这个优化，然后而且你上上不能变，下不能变，就像那接口似的，你是中间一个调用别人调用你，你再调用别人 都不能变，你只能中间做油画，他像一个魔术，就是比如说这个扎握的这个变音器，扎握变音器最开始的时候 说呢，是非很慢的，嗯，非常慢，现在已经接近于这个 c 和 c 加的一个速度了，运行速度他里面就是有很多魔法，所以说他做成了就是一个魔法，跟魔术一样东西很神奇。嗯，但是呢，他 他这坏处就是你，你就只能在中间，你没，其实只能在中间做，然后有很多发挥空间，你可能就没有办法去像写一个新的东西，放飞自我那种发挥限，而且越到后面限制越多，越到后面限制越多。 好，这个我们这个正则表达式，这这节课就讲完了。呃， l l v m。 不会不会， 我我，我在搞那个 circle 的那个编译，还在自己看一些那个普通的一个编程语言，没有去搞那个 l l v m， 其实 l l v m 它它基本上等价于那个 java 的那个字解码， 只不过还扎过资金码，哎，不，我不知道，我忘记哪个出现更早了。他们的那个思路都是一样的，就是通过一种中间的一种资金码，然后，嗯，我保证这个资金码的 变变化小一点，然后大家都兼容这个中间的这个四减码，然后这样那个上层的语法就可以变一下啊。嗯，然后 就是你可挪腾的空间变大了，语法可变的话呢，你那个编器开发的难度就会 会降低，你像那个 c 加加有很多那个兼容历史，那个后来就变得越来越恶心。而像扎我他一开始就用这个扎包，扎包里面的就是这个四节码，四节码的那格式就是相对就基本不变的。他这些年来， 嗯，那些上古时期的那个代码，他都可以通过扎包的方式保存下来。你像很多 c 啊， c 加加那些代码到现在都可能丢了，只有一些二星制，然后那那那个东西就遗失了。 嗯，即使没有仪式，你拿过来以后，他那些语法也和你现在编辑不兼容，那你也很难去把它跑起来，或者是跑好。所以说这个思想还是挺重要的，就是这个 l l v m 或者是 炸包的这种思想。还有那个，呃，新搞出来的叫什么外保苏木林的那那一套也差不多的，就是就是一个一个思路吧。 好，现在不能再说了，现在得睡觉了。嗯，下下播了，关关关，关灯，关电脑。