|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 程序设计语言和语言处理程序知识 > 汇编、编译、解释系统的基本知识和基本工作原理 > 程序语言翻译基础 > 编译程序基本原理 > 词法分析 >
|
|
相关知识点：4个
|
|
|
|
|
|
|
|
|
对于Σ上的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）。
|
|
|
