有限自动机、正规式及其关系

正规表达式(正规式)与正规集

关系

正规集可以用正规式表示
正规式是一种表达正规集的方法
正规集的唯一判定方法是存在对应的正规式

定义

正规式是一种字符集

对于给定字母表∑：

ɛ和⌀都是∑上的正规式；其对应的正规集分别为{ɛ}和⌀（注意区分，它们集合元素数并不一样）
对于a∊∑，a是∑上的正规式；其对应正规集为{a}
(递归拓展)设e1和e2是∑上的正规式，对应的正规集为L(e1)和L(e2)，则
1. (e1|e2)是正规式，正规集为L(e1)∪L(e2) （或）
2. (e1∙e2)是正规式，正规集为L(e1)L(e2) （连接）
3. (e1)*是正规式，正规集为(L(e1))* （闭包）
- 不影响阅读的情况下，可将括号省略
- 由有限次使用上述步骤生成的表达式才能称为∑上的正规式，对应的正规集才能成为∑上的正规集。

正规式的等价性

若两个正规式对应正规集相同，称这两个正规式等价，可以用等号表示。如(a*b*)*=(a|b)*

正规式的性质

（通过转换为正规集来证明）

e1|e2=e2|e1 交换律
(e1|e2)|e3=e1|(e2|e3) 结合律
(e1e2)e3=e1(e2e3) 结合律
e1(e2|e3)=e1e2|e1e3 分配律
(e2|e3)e1=e2e1|e3e1 分配律
eɛ=ɛe=e e1e2≠e2e1

有限自动机/FA

有限自动机是对状态图的形式化定义

确定有限自动机/DFA

它的一个实例常用M来指代。

一个M是一个五元式M=(S, ∑,f,s₀,F)，其中各符号意思为：

S:状态集（有限的）
∑:字母表（有限）
f:状态转换函数，即储存了状态转移关系。映射关系为Sx∑->S，f(s1,a)=s2意为状态s1经过字符a可以转移到状态s2，称s2为s1的一个后继状态。
s₀: s₀∊S，初态（唯一）
F:F⊆S，终态集（可以为空）

一个DFA的例子见下图

实现

参照状态转换图的实现，主要思路是实现状态转移函数，做好初态和终态识别就好。

非确定有限自动机/NFA

类似DFA，实例也以M指代，M=(S, ∑,f,S₀,F)，其中与DFA意义不同的符号为：

S₀:S₀⊆S，初态集（非空，可以有多个）
f:状态转移函数，但映射关系为Sx∑*->(S的幂集，即全部子集)。这个不同暗示了与DFA的2点不同：1 边可以是多个字符拼接的字， 2 从同一个状态且同一个字转移，可以转移到不同的状态（即同一个字可以从同状态射出多条弧）。

可知DFA是NFA的特例

DFA与NFA的关系

对于两个DA M和M'，若L(M)=L(M')，称M和M'等价。
判定两个DA等价的算法存在。
DFA和NFA可以互相转化（即总存在一个另一类的DA与自己等价）
DFA易于实现，NFA易于构造

DFA与NFA的转化

DFA转化为NFA
DFA属于NFA，不赘述。
NFA转化为DFA
按如下步骤：
- 引入新节点X和Y作为新的初态结点和终态结点——方法是从X射出ɛ到所有旧初态，所有旧终态射出ɛ到Y。（解决初态非唯一性）
- 引入一些新结点，来将字符串弧拆分成字符弧（具体方法很显然，不赘述了）
  从而得到了一个新状态转移图，这个图弧上都是字符和ɛ，可能仍然存在同状态同字符多弧的情况。
  下面引入一些概念再继续转换：
  - ɛ-闭包/e-closure(I)
    设I是状态集S的一个子集（一撮状态），则I的ɛ-闭包就是（I合并上所有从I经过若干ɛ弧能到达的所有状态）
  - I_a
    I_a=ɛ-closure(J)，其中J为从I经过若干a弧能到达的所有状态的集合。（换句话说I_a就是从I经过若干ɛ和一个a能到达的状态的集合）
回到转换
不失一般性，设∑仅含a,b。下面列一张状态转换表，来整理实际转换关系：
这个表有三列，第一列是一些状态集（每个设为I），第二列和第三列是对应I的I_a和I_b。
构造这个表的过程如下：
- 第一个状态集是X的ɛ-闭包，算出它的I_a和I_b。
- 观察得到的I_a和I_b是否有出现在第一列，若没有，填入。
- 反复做如上处理，直到第一列没有新增为止。（此时第二三列的所有元素都在第一列了。）
此时得到的这个表刻画了原来的状态转换图实际转换关系（指略去ɛ）。于是我们可以重新构造一个新的状态转化图，图的结点是表的第一列的原图的各种状态子集，它们的连接关系参照第一列和第二列，将含原图初态的子集作为新初态；含原图终态的子集作为新终态——就得到了一个不含ɛ，弧全为字符，初态只有一个的状态转换图，这个图即为与原NFA等价转换而成的DFA。
例子如图

DFA的简化（目标当然是最小化）

先引入一些概念 - 状态的等价性
对于同一个自动机M的两个状态s和t，对于从s到终态能读出的每个字α，也一样能由t到终态读出（两个终态不必一样），反之t的也是这样，则称这两个状态等价。 - 同一个自动机的两个状态不等价时称它们是可区别的。

基本思路

将M的状态集划分为一些不相交的子集，这些子集满足：

异子集的状态都可区别
同子集的状态都等价

最后只要给每一个子集选出一个代表，就可以完全表示出原有的状态机。此时这个状态机已经得到了简化（而且是最小化了）

具体方法

主要思路是将整个状态集不断往下划分，保证每次划分都使得不同子集状态可区别，一直划分到不能继续划分，完成，此时同子集内等价。

（起步）先将S划分为终态和非终态
（步进）检查每个子集，对于一个子集I，若存在一个字符a，有I_a不是现有划分的子集中的任何一个的真子集（即与多于1个子集重叠），那么说明I可以继续划分。就按I中的状态s由a去到的状态所处的子集的不同来划分。
【e.g. 设s1由a到t1；s2由a到t2。而t1,t2属于不同子集，说明存在一个字符α可以区分t1、t2,那么s1和s2可以由aα区分，故s1和s2可以划分开来】
（循环步进，终点判断）反复重复2.，直到无法再划分为止。
（构造新图）将含有原初态的子集作为新的初态，原终态的子集作为新的终态。对于每个子集，选一个结点代表这个子集的所有结点，将从这个子集射出的所有弧都从这个结点射出（记得是射出到其它子集的代表结点），接收的所有弧都给这个点接收（代表结点）。（重复弧删去）删去其它非代表结点。完成化简。

一个例子如下：

正规式和有限自动机的关系

正规式和有限自动机可以互相转化

具体方法

首先先将状态转换图的概念拓广，使得弧上不仅可以通过字符/字，还可以通过正规式

正规式 -> NFA

使用归纳推理。 (以下构造的NFA都要只有一个初态和一个终态，方便证明)

当正规式r中的运算符数目为0时存在正规式由NFA对应。（考虑r=ɛ、r=⌀、r=a三种情况即可，看图）
若结论对于运算符数目小于k时成立，试证明对于数目为k时也成立：有三种情况
1. r=r1|r2
  此时r1,r2结论成立，故设M1对应r1，M2对应r2，用一个新的初态和终态如图连接M1、M2即可得到r对应的NFA M。
2. r=r1r2
  类似地，如图连接即可。
3. r=r1* 如图连接即可。