- 正规式——》最小化DFA
1.先把正则式——》NFA（非确定有穷自动机）
涉及一系列分解规则
2.再把NFA通过"子集构造法"——》DFA
通过子集构造法将NFA转化为DFA
将表里的变量名用比较简单的符号代替（最好是在进行构造的时候顺手在草稿纸上标记好，方便后面的工作）
对照上面的表，画出DFA的状态转换图
图中0,1,2,3,4,5都是终态，因为他们的集合里都包含了最初的终态“数字9”。
3.再把DFA通过"分割法”进行最小化
- 消除多余状态
从这个状态没有通路到达终态；S1
从开始状态出发，任何输入串也不能到达的那个状态。S2
- 合并等价状态
采用“分割法”
兼容性（一致性）条件——同是终态或同是非终态
传播性（蔓延性）条件——对于所有输入符号，状态s和状态t必须转换到等价的状态里。
DFA的最小化—例子，第一步都是固定的。分成终态和非终态
１．将Ｍ的状态分为两个子集一个由终态k1=｛Ｃ，Ｄ，Ｅ，Ｆ｝组成，一个由非终态k2=｛Ｓ，Ａ，Ｂ｝组成，
２．考察｛Ｓ，Ａ，Ｂ｝是否可分．
因为Ａ经过a到达C属于k1.而S经过a到达A属于k2.B经过a到达A属于k2，所以K2继续划分为{S，B},{A},
３．考察｛Ｓ，Ｂ｝是否可再分：
B经过b到达D属于k1.S经过b到达B属于k2，所以S，B可以划分。划分为{S},{B}
４．考察｛Ｃ，Ｄ，Ｅ，Ｆ｝是否可再分：
因为Ｃ，Ｄ，Ｅ，Ｆ经过a和b到达的状态都属于｛Ｃ，Ｄ，Ｅ，Ｆ｝=k1所以相同，所以不可再分：
５．｛Ｃ，Ｄ，Ｅ，Ｆ｝以｛Ｄ｝来代替则，因为CDEF相同，你也可以用C来代替。无所谓的最小化的ＤＦＡ如图，：
“后面这些内容鄙人以为书上都有，列出来整理一下思路、多加练习即可，不必浪费时间敲到电脑上”
- 正则表达式——》正则文法
正则表达式是哟中抽象数学表达式，而正则文法是一种N型文法
由正则表达式转换为正则文法的步骤如下：
- 令开始符号为S，S属于非终结符集，VT等于字符集
- 先生成正规产生式S->r
- 再分解正规产生式S->r,分解规则如下：
（R.1）对形如A->r1r2的正规产生式分解为
·
A->r1B,B->r2,B属于非终结符
（R.2）对形如A->r1*r2的正规产生式分解为
A->rB,A->r1,B->rB,B->r1,B属于非终结符
（R.3）对形如A->r1|r2的正规产生式分解为A->r1,A->r2
不断应用分解规则做变换，知道每个产生式右端只含一个非终结符为止。
- 正则文法——》正则表达式
从正则文法转换为正规表达式，实际上就是一个推倒过程。从开始符号出发，合并正规产生式S->r。合并规则如下：
（R.1）对形如A->xB，B->y的正规产生式合并为A=xy
（R.2）对形如A->xA|y的正规表达式合并为为A=x*y
（R.3）对形如A->x|y的正规产生式合并为A=x|y
如果正规产生式中有相同的左边表达式，可以先合并出发点相同的
- 有限自动机——》正则表达式
转换步骤：
首先加入初态x和终态y，构成一个新的NFA
然后反复使用替换规则，反复使用替换规则逐步消去NFA中的状态节点，直至剩下x，y为止。
- 正则表达式——》有限自动机