正规式转换为不确定的有穷自动机的算法1. 目的与要求：通过设计、编写和调试将正规式转换为不确定的有穷自动机的程序，掌握转换过程中的相关概念和方法，NFA的表现形式可以是图标或者图形2. 问题描述：任意给定一个正规式r（包括链接、或、闭包运算），根据如下算法，设计一个程序，生成与该正规式等价的NFA N.算法：首先，分析给定的正规式r，将其分解成最基本的子表达式，使用下面的规则（1）和规则（2）为r中的每个基本符号（e或字母表中的符号）构造NFA如果符号a在r中出现多次，则要为它的每次出现构造一个NFA然后，使用规则（3）逐步地组合前面构造的NFA，直到获得整个正规式的NFA为止基本规则如下：（1）对于e，构造如下图所示的NFA，它识别{e}；（2）对于Σ中的每个符号a，构造如下图所示的NFA，它识别{a}；（3）如果N(s)和N(t)分别是正规式s和t的NFA，则：[1] 对正规式s∣t，构造合成的NFA N(s∣t)，结果如下图所示：加入x和y节点，从x引e弧到N(s)和N(t)的开始状态，从N(s)和N(t)的接受状态引e弧到y节点；[2] 对正规式st，构造合成的NFA N(st)，结果如下图所示：N(s)的开始状态成为合成后的NFA的开始状态，N(t)的接受状态成为合成后的NFA的接受状态，N(s)的接受状态和N(t)的开始状态合并；[3] 对于正规式s*，构造合成的NFA N(s*)，如下图所示：[4] 对于括号括起来的正规式(s)，使用N(s)本身作为他的NFA.3. 基本要求：（1）输入一个正规式r；（2）输出与正规式r等价的NFA(可以是表格形式或图形形式)。
测试数据：输入正规式：r=(a∣b)*(aa∣bb)(a∣b)*4. 实现提示：（1）NFA的表示可以是图形或者表格形式，状态之间的变换也可以直接表示为每两个状态一组，表示为“起始状态——输入字符——>到达状态”，如“①——a——>②”表示在①状态下读入输入字符a，变换到②状态2）实现时的数据结构的定义：[1] 用字符串存储正规式；[2] 用结构体链表存放状态转换图struct NFA {int from;int to;char varch;}; //表示状态from到达状态to，经过字符varch[3] 中间过程使用堆栈结合正规式算符优先关系表来完成正规式的优先关系表：rstacka*●∣()#aerr>>>err>>*><>>●<<>><>>∣<<<><>>(<<<<<=err)err>>>>err>#<<<<
如：* (a∣b) ● (a●a∣b●b)，●的作用域为* (a∣b)和(a●a∣b●b)尤其要保存●左边的表达式* (a∣b)。