词法分析（编译原理）
正规式和正规文法的相互转换
（正规式即正则表达式，正规文法即3型文法）
1. 对形如A=>x*y的正规式产生式，重写为
A=>xB
A=>y
B=>xB
B=>y,B为一个新的非终结符
2. 对形如A=>x|y的正规式产生式，重写为
A=>x
A=>y
例如：将r=a(a|d)*转换为相应的正规文法
首先，令S为开始符号，则S=a(a|d)*,然后形成S=>aA和A=>(a|d)*
再变换成S=>aA A=>(a|d)B A=>ε B=>(a|d)B B=>ε
最后全部变为符合正规文法的表达式：
S=>aA A=>aB A=>dB B=>aB B=>dB A=>ε B=>ε
| 文法产生式 | 正规式 | |
| 规则1 | A=>xB B=>y | A=xy |
| 规则2 | A=>xA|y | A=x*y |
| 规则3 | A=>x A=>y | A=x|y |
例如：有下列文法G[S]：
S=>aA
S=>a
A=>aA
A=>dA
A=>a
A=>d
首先，进行合并，S=>aA|a, A=(aA|dA)|(a|d)=(a|d)A(a|d)=(a|d)*(a|d)
再将A的右端带入S可得
S=>a(a|d)*(a|d)|a
即S=>a(a|d)*
- 正规文法转换成正规式
- 正规式转换成正规文法
 | |||
|
M = (K,Σ,f,S,Z) 其中：（1）K是一个有穷集，每一个元素是一个状态 （2）Σ是一个有穷字母表，每个元素代表一个输入符号。 （3）f是转换函数，是K*Σ=>K上的全体子集的映像。即K*Σ=>2k,2k表示k的幂集。 （4）S∈K，是唯一的一个初态 （5）Z包含于K，是一个终态集也称为可接受状态或结束状态。
也就是说，最大的不同点在于可以多值映射。例如书上
0状态在读取a之后，可能到0状态，也可能到3状态。是一种一对多的关系。 | |||
确定有穷自动机的化简
最小化问题，采用分割法
首先将子集，按终态和非终态划分为两个子集，然后看子集里的元素等不等价，把等价的元素分在一起。最后，这些等价的子集用其中一个元素表示即可。