编译原理NFA转DFA

1、编译原理实验报告实验名称 不确定有限状态自动机的确定化 实验时间 院系 计算机科学与技术学院 班级 学号 姓名 1.试验目的输入： 非确定有限（穷）状态自动机。输出： 确定化的有限（穷）状态自动机2.实验原理一个确定的有限自动机（DFA）M可以定义为一个五元组，M（K，F，S，Z），其中：（1） K是一个有穷非空集，集合中的每个元素称为一个状态；（2） 是一个有穷字母表，中的每个元素称为一个输入符号；（3） F是一个从K×K的单值转换函数，即F（R，a）Q，（R，QK）表示当前状态为R，如果输入字符a，则转到状态Q，状态Q称为状态R的后继状态；（4） SK，是惟一的初态；（5） ZK

2、，是一个终态集。由定义可见，确定有限自动机只有惟一的一个初态，但可以有多个终态，每个状态对字母表中的任一输入符号，最多只有一个后继状态。 对于DFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFA M所接受。若M的初态结点同时又是终态结点，则称可为M所接受（或识别），DFA M所能接受的全部字符串（字）组成的集合记作L（M）。 一个不确定有限自动机（NFA）M可以定义为一个五元组，M（K，F，S，Z），其中：（1） k是一个有穷非空集，集合中的每个元素称为一个状态；（2） 是一个有穷字母表，中的每个元素称为一个输入符号；（3） F是

3、一个从K×K的子集的转换函数；（4） SK，是一个非空的初态集；（5） ZK，是一个终态集。由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是：（1）NFA的初始状态S为一个状态集，即允许有多个初始状态；（2）NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数。因此，可以将确定有限自动机DFA看作是不确定有限自动机NFA的特例。和DFA一样，NFA也可以用矩阵和状态转换图来表示。对于NFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记（除外）连接形成的

4、字符串可为M所接受。NFA M所能接受的全部字符串（字）组成的集合记作L（M）。由于DFA是NFA的特例，所以能被DFA所接受的符号串必能被NFA所接受。设M1和M2是同一个字母集上的有限自动机，若L（M1）L（M2），则称有限自动机M1和M2等价。由以上定义可知，若两个自动机能够接受相同的语言，则称这两个自动机等价。DFA是NFA的特例，因此对于每一个NFA M1总存在一个DFA M2，使得L（M1）L（M2）。即一个不确定有限自动机能接受的语言总可以找到一个等价的确定有限自动机来接受该语言。NFA确定化为DFA同一个字符串可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都

5、是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。下面介绍一种NFA的确定化算法，这种算法称为子集法：（1） 若NFA的全部初态为S1，S2，Sn，则令DFA的初态为：SS1，S2，Sn，其中方括号用来表示若干个状态构成的某一状态。（2） 设DFA的状态集K中有一状态为Si，Si+1，Sj，若对某符号a，在NFA中有F（ Si，Si+1，Sj ，a）= Si，Si+1，Sk 则令F（ Si，Si+1，Sj ，a）= Si，Si+1，Sk 为DFA的一个转换函数。若 Si，Si+1，Sk 不在K中，则将

6、其作为新的状态加入到K中。（3） 重复第2步，直到K中不再有新的状态加入为止。（4） 上面得到的所有状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表仍然是NFA的字母表。（5） DFA中凡是含有NFA终态的状态都是DFA的终态。对于上述NFA确定化算法子集法，还可以采用另一种操作性更强的描述方式，下面我们给出其详细描述。首先给出两个相关定义。 假设I是NFA M状态集K的一个子集（即IK），则定义-closure（I）为：（1） 若QI，则Q-closure（I）；（2） 若QI，则从Q出发经过任意条弧而能到达的任何状态Q，则Q-closure（I）。状态集-closure（I

7、）称为状态I的闭包。假设NFA M（K，F，S，Z），若IK，a，则定义Ia-closure（J），其中J是所有从-closure（I）出发，经过一条a弧而到达的状态集。NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。3.实验内容（1）根据实验原理，编写对应的算法，并用合适的数据结构加以实现（2）根据算法内容，编写源代码，并进行仔细的调试（3）调试无误后，输入相应的实验数据对程序进行检测4.实验心得实验让我更加深入得了解什么是NFA和DFA，随

8、着实验次数的增多，现在做起实验来更加顺畅了5.实验代码与结果#include "stdafx.h"#include <stdio.h>#include <conio.h>/宏定义#define MAX_NODE 50/允许最多的结点数#define MAX_END 10/允许最多的输入符号数#define MAX_DEGR 8/每个结点允许的最大出度#define MAX_TAB 200/状态转化矩阵最多行数#define BEGIN_STATE0/初始状态结点 int型#define END_STATE -1/终结状态结点 int型#define

9、EMPTY '#'/空代价 char型#define AREA(n,from,to) (n) >= (from) && (n) <= (to) /判断n是否在区间from,to/集合结构体typedef struct musterint memberMAX_NODE;/集合的元素，最多为结点个数int num;/集合的元素个数muster;/函数声明void musInit(muster* a);/初始化a集合void init(void);/初始化函数，将集合等清零void getData(void);/获得用户输入数据void getDataEx

10、pert(void);/获得用户输入数据 专家模式void taxis(muster* a);/排序函数，把集合里的元素按小到大排序bool isEqual(muster* a, muster* b);/判断集合a与b是否相等 注意：判断的两个集合应该已排序void eCLOSURE(muster*a, muster* b); /求a的空字闭包，结果保存到bvoid empty(int a, muster* b);/递归求结点a出发花费空字到达的结点集合void aCLOSURE(muster*a, muster* b, char c);/求a经过一条c弧到达的状态结点全体的空字闭包，结果保存

11、到bint findLocal(int a);/找到结点表示为a的元素在node数组的下标void addMem2Mus(muster* a, int b);/将b加至集合avoid addMus2Mus(muster* a, muster*b);/将集合b加至集合avoid printMus(muster*a);/打印a集合/为了便于处理，这里把一系列变量设置为全局变量int nodeNum;/结点数int endNum;/终结符数char endMAX_END;/终结符int nodeMAX_NODEMAX_DEGR+12;/nodei00保存结点的表示 -2表示开始 -1表示终结/nod

12、ei01存当前结点的出度n/nodei10-nodein+10保存当前结点到下一结点的表示/nodei11-nodein+11 保存字符 当前结点到下一结点的代价muster tabMAX_TABMAX_END + 1;/状态转化矩阵 其元素均为集合类型muster/END 全局变量void musInit(muster* a)/初始化a集合a->num = 0;void init()/初始化函数，将集合等清零int i,j;for(i=0; i<MAX_TAB; +i)for(j=0; j < MAX_END+1; +j)musInit(&tabij);void g

13、etData()/获得用户输入数据int i, j, k;/循环辅助变量bool flg;/在判断输入代价是否合法时用的一个标记/获得合法的终结符数dofflush(stdin);/防止非数字的输入导致死循环 不规范的用法 不推荐printf("nn请输入输入符号表的输入符号总数(1,%d): ", MAX_END);scanf("%d", &endNum);while( !AREA(endNum, 1, MAX_END) );/获得终结符集合for(i=0; i<endNum; +i)fflush(stdin);printf("

14、t输入第 %d 个输入符号: ", i+1);scanf("%c", &endi);printf("n=nn");/获得合法的结点总数dofflush(stdin);/防止非数字的输入导致死循环 不规范的用法 不推荐printf("输入结点总数包括开始和结束结点(1,%d): ", MAX_NODE);scanf("%d", &nodeNum);while( !AREA(nodeNum, 1, MAX_NODE) );/获得各个结点的相关数据for(i=0; i<nodeNum; +

15、i)fflush(stdin);printf("n输入第%d个结点的代号只允许数字表示结点，且规定%d为初态X %d为终态Y: ", i+1, BEGIN_STATE, END_STATE);scanf("%d", &nodei00);if(END_STATE = nodei00)/如果当前结点是终结符则不要去要求输入当前结点的其他数据nodei01 = 0;elsedofflush(stdin);printf("t输入这个结点的出度即有多少条从这个结点出发的弧(0,%d): ", MAX_DEGR);scanf("

16、%d", &nodei01);while( !AREA(nodei01, 0, MAX_DEGR) );for(j=1; j <= nodei01; +j)fflush(stdin);printf("ntt输入当前结点的第 %d 条出发弧所到达的结点: ", j);scanf("%d", &nodeij0);fflush(stdin);flg = true;/获得一个有意义的代价符号即：代价只可能是空或者开始时输入的终结符集合中的一种doprintf("tt输入当前结点的第 %d 条出发弧所花费的代价空弧用%c表

17、示: ", j, EMPTY);fflush(stdin);scanf("%c", &nodeij1);if(nodeij1 = EMPTY)flg = false;for(k=0; k<endNum; +k)if(nodeij1 = endk)flg = false;while(flg);void getDataExpert()/获得用户输入数据 int i, j;/循环辅助变量/获得终结符数printf("nn输入数据数据间用 一个 空格隔开:n");scanf("%d", &endNum);/获得

18、终结符集合for(i=0; i<endNum; +i)getchar();scanf("%c", &endi);/获得合法的结点总数scanf("%d", &nodeNum);/获得各个结点的相关数据for(i=0; i<nodeNum; +i)scanf("%d", &nodei00);if(END_STATE = nodei00)/如果当前结点是终结符则不要去要求输入当前结点的其他数据nodei01 = 0;elsescanf("%d", &nodei01);for(

19、j=1; j <= nodei01; +j)scanf("%d", &nodeij0);getchar();/获得一个有意义的代价符号scanf("%c", &nodeij1);void taxis(muster* a)/排序函数，把集合里的元素按小到大排序int i, j;/循环辅助int temp;/临时变量交换值/简单的冒泡排序 for(i=1; i < a->num; +i)for(j=0; j < i; +j)if(a->memberj > a->memberi)temp = a->

20、;memberi;a->memberi = a->memberj;a->memberj = temp;bool isEqual(muster* a, muster* b)/判断集合a与b是否相等 注意：判断的两个集合应该已排序int i;if(a->num != b->num)/元素个数不相等则集合不相等return false;for(i=0; i < a->num; +i)if(a->memberi != b->memberi)return false;return true;void eCLOSURE(muster*a, muster

21、* b) /求a集合的空字闭包，结果保存到bint i;muster tmp;musInit(&tmp);addMus2Mus(b, a);/集合a本身是属于a的空字闭包for(i=0; i<a->num; +i)/分别求出a集合的每个元素的空字闭包保存到bempty(a->memberi, &tmp);addMus2Mus(b, &tmp);void aCLOSURE(muster*a, muster* b, char c) /求a经过一条c弧到达的状态结点全体的空字闭包/结果保存到bint xb;int i, j;muster tmp;musIni

22、t(&tmp);/求a经过一条c弧到达的状态结点全体 保存在tmp集合for(i=0; i<a->num; +i)xb = findLocal(a->memberi);/找到结点表示为a->memberi的元素在node数组的下标/遍历a->memberi结点的所有出度for(j=1; j <= nodexb01; +j)if(c = nodexbj1)/到下一结点代价为c则保存下一结点到集合addMem2Mus(&tmp, nodexbj0);/再求tmp集合的空字闭包 结果保存在集合beCLOSURE(&tmp,b);void e

23、mpty(int a, muster* b)/递归求结点a出发花费空字到达的结点集合int xb;int i;if(a = END_STATE)/当前结点是终点则不再往下找return;xb = findLocal(a);/找到结点表示为a的元素在node数组的下标/遍历a结点的所有出度for(i=1; i <= nodexb01; +i)if(nodexbi1 = EMPTY)/到下一结点空代价addMem2Mus(b, nodexbi0);/将下一结点保存到集合empty(nodexbi0, b);/递归过程int findLocal(int a)/找到结点表示为a的元素在node数

24、组的下标int i;for(i=0; i<nodeNum; +i)if(a = nodei00)return i;printf("na错误！无法在结点集合中找到标记为 %d 的结点，请检查你的输入!nn", a);return -1;void addMem2Mus(muster* a, int b)/将b加至集合aint i;for(i=0; i<a->num; +i)if(b = a->memberi)break;/只有当前集合中没有b元素才将b加入if(i >= a->num)a->membera->num+ = b;ta

25、xis(a);/排序void addMus2Mus(muster* a, muster*b)/将集合b加至集合aint i;for(i=0; i<b->num; +i)addMem2Mus(a, b->memberi);void printMus(muster*a)/打印a集合int i;if(0 = a->num)/空集合printf(" - ");return;printf("");for(i=0; i<a->num; +i)switch(a->memberi)case BEGIN_STATE:printf(

26、"X");break;case END_STATE:printf("Y");break;default:printf("%d", a->memberi);(i = a->num - 1) ? printf("") : printf(" , ");/入口函数int main()int i, j, k;int searchx, searchy, lastx, lasty; muster tmp;musInit(&tmp);init();/获取输入数据printf(" N

27、FA转DFA算法实现nn请按回车键后照提示操作：");if(getch() = ' ')getDataExpert();elsegetData();/子集法生成状态转化矩阵/处理转化矩阵第一行empty(BEGIN_STATE, &tmp);/从开始符开始addMem2Mus(&tmp, BEGIN_STATE);/包括开始符本身addMus2Mus(&tab00, &tmp);for(j=1; j<endNum+1; +j)/矩阵每行有endNum+1个集合aCLOSURE(&tab00, &tab0j, end

28、j-1);searchx = 0; searchy = 1;lastx = 0; lasty = endNum;/处理转换矩阵的其他行for(i=1; ; +i)/至于矩阵有多少行，是要动态决定的if(i >= MAX_TAB)printf("nta状态转化矩阵越界，请修改状态转化矩阵的最大行数宏nn");break;lastx = i-1;/确定Ifor(; searchx <= lastx; +searchx)if(searchy > endNum)/这个判断非常重要searchy = 1;for(; searchy <= lasty; +sea

29、rchy)/判断tabsearchxsearchy是否要插入第一列for(k=0; k <= lastx; +k)if (isEqual(&tabsearchxsearchy, &tabk0)break;/如果没有重复的而且当前集合非空则要把tabsearchxsearchy插入当前行的第一列if(tabsearchxsearchy.num !=0 && k > lastx)addMus2Mus(&tabi0, &tabsearchxsearchy);goto endsearch;/这里必须用goto跳转到多曾循环外/虽然goto的使用大有争论但是这里采用其不会对程序的理解和维护带来麻烦/else如果有重复的或者是空则我们转到下一个集合判断/当所有的集合都判断完了 则我们的转化过程也完成了if(searchx > lastx)break;endsearch:/确定Ia Ib .for(j=1; j<endNum+1; +j)/矩阵每行有endNum+1个集合aCLOSURE(&tabi0, &tabij, endj-1);printf("通过子集法求得的状态转换矩阵为:n It&quo