📄 nfa转化为dfa.cpp
字号:
/**
NFA转化为DFA
本程序用数组这一简单的线性数据结构来解决复杂的状态转化图问题
其实对于这类问题可以采用图结构[或者干脆转化为带环的多叉树结构]
程序内有多处可以作大量优化 比如：排序函数的实现、需要排序的条
件、空字闭包的求法 ... ... 懒的优化了 写这个程序也只是为了自己
做作业方便[:)]，乖乖，作业上的状态转换矩阵那个壮观啊，手工写难
免有少许失误，而一旦有一处失误将导致最终结果错误。
04计算08宁尚昆[Ninstein] @ 22:42 2007-3-26
Welcome to www.ninstein.com www.nskun.cn
*/
/*
Test[采用的本程序附带数据而非手工输入数据]:
通过子集法求得的状态转换矩阵为:
I Ia Ib
--------------------------
{X , 2} {Y , 1} {Y , 3}
{Y , 1} ---- {Y}
{Y , 3} ---- ----
{Y} ---- ----
重命名后的状态转化矩阵为:
I Ia Ib
--------------
0 1 2
1 -- 3
2 -- --
3 -- --
Press any key exit.
*/
#include <stdio.h>
#include <conio.h>
//宏定义
#define MAX_NODE 100 //允许最多的结点数
#define MAX_END 20 //允许最多的终结符数
#define MAX_DEGR 8 //每个结点允许的最大出度
#define MAX_TAB 200 //状态转化矩阵最多行数
#define BEGIN_STATE -2 //初始状态结点 int型
#define END_STATE -1 //终结状态结点 int型
#define EMPTY '#' //空代价 char型
#define AREA(n,from,to) (((n) >= (from)) && ((n) <= (to))) //判断n是否在区间[from,to]
//集合结构体
typedef struct muster
{
int member[MAX_NODE]; //集合的元素，最多为结点个数
int num; //集合的元素个数
}muster;
//函数声明
void musInit(muster* a); //初始化a集合
void init(void); //初始化函数，将集合等清零
void getData(void); //获得用户输入数据
void getDataExpert(void); //获得用户输入数据 专家模式
void taxis(muster* a); //排序函数，把集合里的元素按小到大排序
bool isEqual(muster* a, muster* b); //判断集合a与b是否相等 注意：判断的两个集合应该已排序
void eCLOSURE(muster*a, muster* b); //求a的空字闭包，结果保存到b
void empty(int a, muster* b); //递归求结点a出发花费空字到达的结点集合
void aCLOSURE(muster*a, muster* b, char c);//求a经过一条c弧到达的状态结点全体的空字闭包，结果保存到b
int findLocal(int a); //找到结点表示为a的元素在node数组的下标
void addMem2Mus(muster* a, int b); //将b加至集合a
void addMus2Mus(muster* a, muster*b);//将集合b加至集合a
void printMus(muster*a); //打印a集合
//为了便于处理，这里把一系列变量设置为全局变量
int nodeNum; //结点数
int endNum; //终结符数
char end[MAX_END]; //终结符
int node[MAX_NODE][MAX_DEGR+1][2];
//node[i][0][0]保存结点的表示 -2表示开始 -1表示终结
//node[i][0][1]存当前结点的出度n
//node[i][1][0]--node[i][n+1][0]保存当前结点到下一结点的表示
//node[i][1][1]--node[i][n+1][1] 保存字符 当前结点到下一结点的代价
muster tab[MAX_TAB][MAX_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(&tab[i][j]);
}
void getData() //获得用户输入数据
{
int i, j, k; //循环辅助变量
bool flg; //在判断输入代价是否合法时用的一个标记
//获得合法的终结符数
do
{
fflush(stdin); //防止非数字的输入导致死循环 不规范的用法 不推荐
printf("\n\n输入终结符总数([1,%d]): ", MAX_END);
scanf("%d", &endNum);
}while( !AREA(endNum, 1, MAX_END) );
//获得终结符集合
for(i=0; i<endNum; ++i)
{
fflush(stdin);
printf("\t输入第 %d 个终结符: ", i+1);
scanf("%c", &end[i]);
}
printf("\n=============================\n\n");
//获得合法的结点总数
do
{
fflush(stdin); //防止非数字的输入导致死循环 不规范的用法 不推荐
printf("输入结点总数[包括开始和结束结点]([1,%d]): ", MAX_NODE);
scanf("%d", &nodeNum);
}while( !AREA(nodeNum, 1, MAX_NODE) );
//获得各个结点的相关数据
for(i=0; i<nodeNum; ++i)
{
fflush(stdin);
printf("\n输入第%d个结点的代号[只允许数字%d为X %d为Y]: ", i+1, BEGIN_STATE, END_STATE);
scanf("%d", &node[i][0][0]);
if(END_STATE == node[i][0][0]) //如果当前结点是终结符则不要去要求输入当前结点的其他数据
{
node[i][0][1] = 0;
}
else
{
do
{
fflush(stdin);
printf("\t输入这个结点的出度[即有多少条从这个结点出发的弧]([0,%d]): ", MAX_DEGR);
scanf("%d", &node[i][0][1]);
}while( !AREA(node[i][0][1], 0, MAX_DEGR) );
for(j=1; j <= node[i][0][1]; ++j)
{
fflush(stdin);
printf("\n\t\t输入当前结点的第 %d 条出发弧所到达的结点: ", j);
scanf("%d", &node[i][j][0]);
fflush(stdin);
flg = true;
//获得一个有意义的代价符号[即：代价只可能是空或者开始时输入的终结符集合中的一种]
do
{
printf("\t\t输入当前结点的第 %d 条出发弧所花费的代价[空弧用%c表示]: ", j, EMPTY);
fflush(stdin);
scanf("%c", &node[i][j][1]);
if(node[i][j][1] == EMPTY)
flg = false;
for(k=0; k<endNum; ++k)
{
if(node[i][j][1] == end[k])
flg = false;
}
}while(flg);
}
}
}
}
void getDataExpert() //获得用户输入数据 专家模式
{
int i, j; //循环辅助变量
//获得终结符数
printf("\n\n输入数据[数据间用 一个 空格隔开]:\n");
scanf("%d", &endNum);
//获得终结符集合
for(i=0; i<endNum; ++i)
{
getchar();
scanf("%c", &end[i]);
}
//获得合法的结点总数
scanf("%d", &nodeNum);
//获得各个结点的相关数据
for(i=0; i<nodeNum; ++i)
{
scanf("%d", &node[i][0][0]);
if(END_STATE == node[i][0][0]) //如果当前结点是终结符则不要去要求输入当前结点的其他数据
{
node[i][0][1] = 0;
}
else
{
scanf("%d", &node[i][0][1]);
for(j=1; j <= node[i][0][1]; ++j)
{
scanf("%d", &node[i][j][0]);
getchar();
//获得一个有意义的代价符号
scanf("%c", &node[i][j][1]);
}
}
}
}
void taxis(muster* a) //排序函数，把集合里的元素按小到大排序
{
int i, j; //循环辅助
int temp; //临时变量交换值
//简单的冒泡排序 有兴趣优化此排序算法 会对整个运算提高比较高的效率
for(i=1; i < a->num; ++i)
for(j=0; j < i; ++j)
{
if(a->member[j] > a->member[i])
{
temp = a->member[i];
a->member[i] = a->member[j];
a->member[j] = 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->member[i] != b->member[i])
return false;
return true;
}
void eCLOSURE(muster*a, muster* b) //求a集合的空字闭包，结果保存到b
{
int i;
muster tmp;
musInit(&tmp);
addMus2Mus(b, a); //集合a本身是属于a的空字闭包
for(i=0; i<a->num; ++i) //分别求出a集合的每个元素的空字闭包保存到b
{
empty(a->member[i], &tmp);
addMus2Mus(b, &tmp);
}
}
void aCLOSURE(muster*a, muster* b, char c) //求a经过一条c弧到达的状态结点全体的空字闭包
//结果保存到b
{
int xb;
int i, j;
muster tmp;
musInit(&tmp);
//求a经过一条c弧到达的状态结点全体 保存在tmp集合
for(i=0; i<a->num; ++i)
{
xb = findLocal(a->member[i]); //找到结点表示为a->member[i]的元素在node数组的下标
//遍历a->member[i]结点的所有出度
for(j=1; j <= node[xb][0][1]; ++j)
{
if(c == node[xb][j][1]) //到下一结点代价为c则保存下一结点到集合
addMem2Mus(&tmp, node[xb][j][0]);
}
}
//再求tmp集合的空字闭包 结果保存在集合b
eCLOSURE(&tmp,b);
}
void empty(int a, muster* b) //递归求结点a出发花费空字到达的结点集合
{
int xb;
int i;
if(a == END_STATE) //当前结点是终点则不再往下找
return;
xb = findLocal(a); //找到结点表示为a的元素在node数组的下标
//遍历a结点的所有出度
for(i=1; i <= node[xb][0][1]; ++i)
{
if(node[xb][i][1] == EMPTY) //到下一结点空代价
{
addMem2Mus(b, node[xb][i][0]); //将下一结点保存到集合
empty(node[xb][i][0], b); //递归过程
}
}
}
int findLocal(int a) //找到结点表示为a的元素在node数组的下标
{
int i;
for(i=0; i<nodeNum; ++i)
if(a == node[i][0][0])
return i;
printf("\n\a错误！无法在结点集合中找到标记为 %d 的结点，请检查你的输入!\n\n", a);
return -1;
}
void addMem2Mus(muster* a, int b) //将b加至集合a
{
int i;
for(i=0; i<a->num; ++i)
if(b == a->member[i])
break;
//只有当前集合中没有b元素才将b加入
if(i >= a->num)
{
a->member[a->num++] = b;
taxis(a);//排序
}
}
void addMus2Mus(muster* a, muster*b) //将集合b加至集合a
{
int i;
for(i=0; i<b->num; ++i)
addMem2Mus(a, b->member[i]);
}
void printMus(muster*a) //打印a集合
{
int i;
if(0 == a->num)
{//空集合
printf(" ---- ");
return;
}
printf("{");
for(i=0; i<a->num; ++i)
{
switch(a->member[i])
{
case BEGIN_STATE:
printf("X");
break;
case END_STATE:
printf("Y");
break;
default:
printf("%d", a->member[i]);
}
(i == a->num - 1) ? printf("}") : printf(" , ");
}
}
//入口函数
int main()
{
int i, j, k;
int searchx, searchy, lastx, lasty;
muster tmp;
musInit(&tmp);
/**测试数据，如果你要调试此程序可以将此部分加入代码中
//然后将下面的 getData(); 函数注释掉 这样就不要手工输入数据
nodeNum = 5; //结点数
endNum = 2; //终结符数
end[0] = 'a', end[1] = 'b'; //终结符
node[0][0][0] = BEGIN_STATE;
node[0][0][1] = 3;
node[0][1][0] = 1;
node[0][1][1] = 'a';
node[0][2][0] = 2;
node[0][2][1] = '#';
node[0][3][0] = 3;
node[0][3][1] = 'b';
node[1][0][0] = 1;
node[1][0][1] = 1;
node[1][1][0] = END_STATE;
node[1][1][1] = 'b';
node[2][0][0] = 2;
node[2][0][1] = 1;
node[2][1][0] = END_STATE;
node[2][1][1] = 'a';
node[3][0][0] = 3;
node[3][0][1] = 1;
node[3][1][0] = END_STATE;
node[3][1][1] = '#';
node[4][0][0] = END_STATE;
node[4][0][1] = 0;
/*/
init();
//获取输入数据
printf("采用专家模式输入空格否则输入其他键(如果你是首次使用请不要采用专家模式) ");
if(getch() == ' ')
getDataExpert();
else
getData();
//子集法生成状态转化矩阵
//处理转化矩阵第一行
empty(BEGIN_STATE, &tmp); //从开始符开始
addMem2Mus(&tmp, BEGIN_STATE); //包括开始符本身
addMus2Mus(&tab[0][0], &tmp);
for(j=1; j<endNum+1; ++j) //矩阵每行有endNum+1个集合
{
aCLOSURE(&tab[0][0], &tab[0][j], end[j-1]);
}
searchx = 0; searchy = 1;
lastx = 0; lasty = endNum;
//处理转换矩阵的其他行
for(i=1; ; ++i) //至于矩阵有多少行，是要动态决定的
{
if(i >= MAX_TAB)
{
printf("\n\t\a状态转化矩阵越界，请修改状态转化矩阵的最大行数宏\n\n");
break;
}
lastx = i-1;
//确定I
for(; searchx <= lastx; ++searchx)
{
if(searchy > endNum) //这个判断非常重要，这个BUG找的我好苦啊~~~
searchy = 1;
for(; searchy <= lasty; ++searchy)
{
//判断tab[searchx][searchy]是否要插入第一列
for(k=0; k <= lastx; ++k)
{
if (isEqual(&tab[searchx][searchy], &tab[k][0]))
break;
}
//如果没有重复的而且当前集合非空则要把tab[searchx][searchy]插入当前行的第一列
if(tab[searchx][searchy].num !=0 && k > lastx)
{
addMus2Mus(&tab[i][0], &tab[searchx][searchy]);
goto endsearch; //这里必须用goto跳转到多曾循环外
//虽然goto的使用大有争论但是这里采用其不会对程序的理解和维护带来麻烦
}
//else如果有重复的或者是空则我们转到下一个集合判断
}
}
//当所有的集合都判断完了 则我们的转化过程也完成了
if(searchx > lastx)// && searchy > lasty 为什么可以去掉这部分判断？仔细思考下吧 呵呵
{
break;
}
endsearch:
//确定Ia Ib ....
for(j=1; j<endNum+1; ++j) //矩阵每行有endNum+1个集合
{
aCLOSURE(&tab[i][0], &tab[i][j], end[j-1]);
}
}
printf("通过子集法求得的状态转换矩阵为:\n I\t");
for(i=0; i<endNum; ++i)
printf(" I%c\t", end[i]);
printf("\n--------------------------\n");
for(i=0; i<=lastx; ++i)
{
for(j=0; j <= endNum; ++j)
{
printMus(&tab[i][j]);
printf("\t");
}
printf("\n");
}
int predigest[MAX_TAB][MAX_END + 1];//简化矩阵
int l;
int flag = 0;
//下面来对上面的tab矩阵进行重命名吧
for(i=0; i<=lastx; ++i)
{
for(j=0; j<=endNum; ++j)
{
if(0 == tab[i][j].num)
{
predigest[i][j] = -1;
continue;
}
for(k=0; k<=i; ++k)
{
for(l=0; l<=endNum; ++l)
{
if(k == i && l > j)
break;
if(/*i!=k && j!=l*/(i!=k || j!=l) && isEqual(&tab[i][j], &tab[k][l]))
//条件i!=k && j!=l改为(i!=k || j!=l) 这个BUG到今天检查作业才发现：（
//至于修改原因很简单，你可以去想想 呵呵
{//如果当前比较的元素不是自身(tab[i][j])，并且与自身相等，则保存重复值
predigest[i][j] = predigest[k][l];
goto endfind;
}
}//end for l
}//end for k
if(k > i && l > j)
predigest[i][j] = flag++;
endfind:;
}//end for j
}//end for i
printf("\n重命名后的状态转化矩阵为:\n I");
for(i=0; i<endNum; ++i)
printf(" I%c", end[i]);
printf("\n--------------\n");
for(i=0; i<=lastx; ++i,printf("\n"))
for(j=0; j<=endNum; ++j)
(predigest[i][j] == -1) ? printf(" --") : printf("%4d",predigest[i][j]);
fflush(stdin);
printf("\n\n\tPress any key exit.");
getch();
return 0;
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -