词法分析器：
正规表达式与有限自动机
三个问题：
正规式<->NFA
NFA->DFA
DFA->化简
一些概念：
我们可以把具有相同特征的字放在一起组成一个集合，即所谓的正规集，
然后使用一种形式化的方法来表示正规集，即所谓的正规式
（1)ε和φ是∑上的正规式,它们所表示的正规集分别为{ε}和φ
(2)任何a∈∑,是∑上的一个正规式,他所表示的正规集为{ a }
(3)假定U和V都是∑上的正规式，他们所表示的正规集分别记为L(U)和L(V)，那么
(a) (U|V)是正规式，所表示的正规集为L(U)∪L(V)
(b) (UV)是正规式，所表示的正规集为L(U) · L(V)（连接积）
(c) (U)*是正规式，所表示的正规集为 (L(U))*（闭包）
仅由有限次使用(1)(2)(3)所得到的表达式才是∑上的正规式，仅由这些正规式所表示的字集才是∑上的正规集
两个正规式的等价：若两个正规式U和V所表示的正规集相同，则认为二者等价，记为：U = V
设U，V，W是上的∑正规式，则
(1) U | V = V | U 或的交换律
(2) U | ( V|W ) = ( U|V ) | W 或的结合律
(3) U ( VW ) = ( UV ) W 连接积的结合律
(4) U ( V | W ) = ( UV ) | ( UW ) 分配律
( V | W ) U = VU | WU
(5) εU = Uε = U
确定的有限自动机（DFA）（Deterministic Finite Automata)
一个确定有限自动机（DFA）M是一个五元式：
M = (S, ∑, f, s0, F)，其中
S是一个有限的状态集合，它的每个元素我们称为一个状态
∑是一个有穷的输入符号的字母表，它的每个元素我们称为一个输入字符
f是从 S×∑ →S的单值部分映射
s0是S的一个元素，为初始状态，它是唯一的
状态集合F是终止状态的集合，它是S的子集(可空)
非确定的有限自动机（NFA）（Non-deterministic Finite Automata)
一个非确定有限自动机（NFA）M是一个五元式
M = (S, ∑, f, S0, F)，其中
S是一个有限的状态集合，它的每个元素我们称为一个状态
∑是一个有限的输入符号的字母表，它的每个元素我们称为一个输入字符
f是从S×∑*→2S 的部分映射，其中，2S表示S的幂集合（所有S的子集组成的集合）（f是非单值的M是非确定）
状态集合S0是初始状态集合，它是S的子集
状态集合F是终止状态的集合，它是S的子集
有限自动机的等价：对任何两个有限的自动机M1和M2，若有L(M1)=L(M2)，则称M1与M2等价
* 若M的某些结点既是初态结点又是终态结点，或者存在一条从某初态结点到某个终态结点的ε通路，那么空字ε可为M所识别
* DFA是NFA的一个特例，对于每个NFA M存在一个DFA M’使得L(M) = L(M’)，也就是说M和M’是等价的
*****正规式与有限自动机的等价性：
定理1：对于任何∑上NFA M都可构造一个∑上的正规式V，使得 L(V) = L(M) ，其中，L(M)是∑上NFA M所能识别的字的全体
L(V)是∑上的正规集
**NFA M构造正规式
(1)在M转换图上加进X结点和Y结点，从X结点用弧ε连接M的所有初态结点，M的所有终态结点用弧ε连接到Y，得到一个NFA M’，且L(M) = L(M’)
(2)使用替换规则逐步消去M’的所有结点，直到只剩下X结点和Y结点，在消去过程中，逐步使用正规式来标记箭弧
定理2：对于∑上的每一个正规式V，存在一个∑上的DFA M，使得L(M) = L(V)
**正规式V，构造一个DFA M
1.根据V，构造一个NFA M’，使得L(M’) = L(V)
2.将M’确定化，变为DFA M
课本例题7.1：
解题思路：
第一步，在∑上构造一个NFA M’
(1)构造一个拓广的转换图
(2)使用分裂规则对V进行分裂，加进新结点，直到把图转换成每条弧上标识为∑上的一个字符或ε，最后得到一个NFA M’
且L(M’) = L(V)
第二步，把M’确定化
定义1：假定I是M’的状态集的子集，定义I的ε闭包ε_CLOSURE(I)为：
(a)若q∈I，则q∈ε_CLOSURE(I)
(b)若q∈I，那么从q出发经任意条ε弧而能到达的任何状态q’都属于ε_CLOSURE(I) ；
定义2：假定I是M’的状态集的子集，a ∈ ∑，定义
Ia =ε_CLOSURE(J)
其中，J是所有那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体
求Ia 可以分为两步：
根据集合I，求集合J（一条a弧）
求J的ε闭包ε_CLOSURE(J)，即是Ia
*****确定有限自动机的化简（最少化）
**DFA化简
(1) 检查状态转换函数是否为全函数。
所谓全函数，是指每个状态对每个输入符号都有转换
若不是全函数，可以引入一个“死状态”d，d对所有输入符号都转换到d，如果状态s对输入符号a没有转换，那么加上从s到d的a转换。
(2) 用化简算法进行化简
(3) 去掉死状态
化简算法
①对M的状态集S进行划分：
把S的终态和非终态分开，分成终态集合非终态集，形成基本分划П，显然这两个子集是可区别的。②假定到某个时候П含有m个子集，
记П={I(1),I(2),… I(m)}
并且，属于不同子集的状态是可区别的。
检查П中的每个I(i)看能否进一步划分：
对于某个I(i)，令I(i)={q1 ,q2 ,…,qk}
若存在一个输入字符a使得I(i)a不全包含在现行П的某个子集I(j)中，就将I(i)一分为二
课本例题12（b）
感悟：
说是从课件上粘贴概念毫无意义却还是粘了觉得这些东西重要一点，再说说我自己的理解，这章词法分析，目的是产生一个词法分析器，我们先粗略的说了一下词法分析器的若干概念，重点却又放在正规式，正规集，利用正规式去产生自动机，自动机和正规式之间能够互相转化根据性质，自动机分为确定的有限和不确定的有限，其中DFA又是NFA的一个特例，NFA能够转化成DFA,DFA又能进行化简得到最小的DFA,课本上的题应用类的还是不是很明白，可能做那种简单的化简转化题不是问题，但是过河或者自己设计的应用类问题还是一头雾水，没有那种学以致用的思维很难受。