|
|
|
|
| 对于Σ上的NFAM，可以构造一个Σ上的正规式R，使得L（R）=L（M）。
|
|
|
| 拓广状态转换图的概念，令每条弧可用一个正规式作标记。为Σ上的NFAM构造相应的正规式R，分为如下两步：
|
|
|
| 第一步：在M的状态转换图中加两个节点，一个x节点，一个y节点。从x节点到NFAM的初始状态节点引一条弧并用ε标记，从NFAM的所有终态节点到y节点引一条弧并用ε标记。形成一个与M等价的M'，M'只有一个初态x和一个终态y。
|
|
|
| 第二步：按下面的方法逐步消去M'中除x和y的所有节点。在消除节点的过程中，用正规式来标记弧，最后节点x和y之间弧上的标记就是所求的正规式。消除节点的规则如下图所示。
|
|
|
|
|
|
|
|
|
| 同样地，对于Σ上的每个正规式R，可以构造一个Σ上的NFAM，使得L（M）=L（R）。
|
|
|
|
|
|
|
|
|
| ②通过对正规式R进行分裂并加入新的节点，逐步把图转变成每条弧上的标记是∑上的一个字符或ε，转换规则如下图所示。
|
|
|
|
|
|
|
| 最后所得的图即为一个NFAM，x为初态节点，y为终态节点。显然，L（M）=L（R）。
|
|
|
