本文主要来源于上课笔记

例：ω∈(a,b)? 且倒数第3个是a :

词法分析：RE?FA? 词法分析程序

FA: 状態数目有限，是一个有始有终的过程模型

表示字母表s0 表示开始状态，F 表示结束状态集/终止状态集move 表示映射

第3张图是一个?? 闭包

I′′′′0=I′′′0??=I′′′0

我们规定初始状态是I0，然后这个状态是要算出来的因为要算闭包

由于{5,3,1} 这个状态不存在，我们命名为I1

最终所有的状態都应该由上面? 闭包或子集构造得到

结论1： 最多情况下由2n?1 种状态，其中n 的个数 减去的一个是空集。

结论2：核相同则??c 相同

总嘚思想是，减少状态数使用的方法是，等价类划分使用聚类的思想。

在这里我们需要将Ii 以终态、非终态划分

1. 对应的标记相同（就是箭頭上面的标记）

易见这是一个递归定义

若两个状态相同，则两个状态等价（强等价）

若后继状态相同，则两个状态等价（强等价）

若后继状态属于同一个已存在的叶节点，则弱等价

由一开始的初始态和终态，得出上图

此时可见I1 在左边，I3 在右边因此将I0,I2 划分到左边，I1 划分到右边得到上图。

在每个叶节点中选一个节点在最右边的叶节点中选I3

注意，需要用到look back 来检查是否之前的后继状态在同一节点而の后的后继状态不在同一节点的情况

一些RE转NFA的规则(人喜欢的方法，也是考试时用的方法)：

方法2是龙书上的算法笔记上有，由於考试不考实验要用，因此现在先不管以后再说。

一个词法分析程序分析所有单词