simple_dfa.c

DFA状态最少化的算法

/*
*  DFA状态最少化的算法.
*/
#include "stdio.h"
#include "conio.h"
#include "malloc.h"
#include "string.h"

#define X -2  /*初始状态X的宏定义*/
#define Y -1  /*最终状态Y的宏定义*/
#define Max_State_Num 32  /*最多新产生的状态的个数*/
#define Max_Marshal_Size 16  /*状态组成的集合的大小*/
#define TRUE 1
#define FALSE 0
/*----------------------------------------------------------------*/
/*
*  输入文件内容存放结构体.
*/
typedef struct Read_temp_File
{
  int start;  /*有向弧的起始start状态*/
  char ShiZi[32];  /*从start状态到end状态的转换式*/
  int end;    /*有向弧的到达的end状态*/
} Read;
/*----------------------------------------------------------------*/
Read READ[32];  /* 全局变量READ[32],是弧的存储结构 */

/* 一个可以查询的状态字典 */
int State_dictionary[Max_State_Num][Max_Marshal_Size + 1];

int dictionary_num = 0;  /* 状态字典里的个数 */
int read_num = 0;  /* DFA的状态变换个数 */

/*
*  记录拆分过程的数组,第二维的大小是18：
*  第一位是有多少个,最后一位是判断是否可以再拆分
*  若为1是可以拆分,0为不可以.
*/
int Register_Split_Process[Max_State_Num][Max_Marshal_Size + 2];
int Mar_Num = 2;
/*----------------------------------------------------------------*/
/*
*  函数预先声明
*
*/
void Read_from_File();

void PrintInput();

void Find_A_B_Marshal();

void Main_Control_Function();

void Initialization();

void FuZhi(int Array1[],int Array2[]);

void Search_BelongTo(int Begin_Mar[],char change[],
					 int Belong_Which_Mar[]);

int Is_Same_Species(int Belong_Which_Mar[]);

void Insert_Split_Result(int Begin_Mar[],int Belong_Which_Mar[]);

void Remove_Prolixity(int result[]);

void Oppsite_Result(int result[],int oppsite[]);
/*----------------------------------------------------------------*/
/* main() */
void main()
{
	int i=0,j,flag;
	int result[16],oppsite[16];

	Read_from_File();
	PrintInput();
	Main_Control_Function();Register_Split_Process[Max_State_Num][Max_Marshal_Size + 2];

	Remove_Prolixity(result);
    Oppsite_Result(result,oppsite);
    
	printf("\n--------------将DFA简化后的结果:--------------\n");

	for(i=0;i<read_num-1;i++)
	{
		flag = TRUE;
		for(j=1;j<=oppsite[0];j++)
			if(oppsite[j]==READ[i].start||oppsite[j]==READ[i].end)
			{
				flag = FALSE;
				break;
			}
		if(flag)
		{
			printf("Start:%d\t\tInput:%s\t\tEnd:%d\n",
				READ[i].start,READ[i].ShiZi,READ[i].end);
		}
	}
}
/*
*  Remove_Prolixity(int result)函数是除去冗余状态
*/
void Remove_Prolixity(int result[])
{
	int i;
	result[0]=0;
	for(i=0;i<Max_State_Num;i++)
	{
		if(Register_Split_Process[i][0]>0&&
			Register_Split_Process[i][17]==0)
		{
			result[0]++;
			result[result[0]]=Register_Split_Process[i][1];
			continue;
		}
	}
}
/*
*  Oppsite_Result(int result)函数是求result的补集.
*/
void Oppsite_Result(int result[16],int oppsite[16])
{
	int i=0,j,flag = TRUE;
	oppsite[0]=0;
	for(i=0;i<dictionary_num;i++)
	{
		flag = TRUE;
		for(j=1;j<=result[0];j++)
		{
			if(result[j] == i)
			{
				flag = FALSE;
				break;
			}
		}
		if(flag)
		{
			oppsite[0]++;
			oppsite[oppsite[0]] = i;
		}
	}
}
/*
*  Main_Control_Function()函数是程序的主要控制函数.
*/
void Main_Control_Function()
{
	int Begin_Mar[Max_Marshal_Size+2];
	int Belong_Which_Mar[Max_Marshal_Size+2];
	int i,j,temp;
	
	Initialization();

	for(i=0;i<2;i++)
	{
		FuZhi(Begin_Mar,Register_Split_Process[i]);
		Search_BelongTo(Begin_Mar,"a",Belong_Which_Mar);
		if(!Is_Same_Species(Belong_Which_Mar))
	    	Insert_Split_Result(Begin_Mar,Belong_Which_Mar);

		if(Is_Same_Species(Belong_Which_Mar))
		{
			Search_BelongTo(Begin_Mar,"b",Belong_Which_Mar);
			if(Is_Same_Species(Belong_Which_Mar))
			{
				Register_Split_Process[i][17]=FALSE;
				continue;
			}
			else{
				Insert_Split_Result(Begin_Mar,Belong_Which_Mar);
				temp = Mar_Num-2;
				for(j=temp;j<=temp+1;j++)
					Register_Split_Process[j][17]=FALSE;
			}
		}
		else{
            temp = Mar_Num-2;
			for(j=temp;j<=temp+1;j++)
			{
				FuZhi(Begin_Mar,Register_Split_Process[j]);
				if(Begin_Mar[17]==0)
					continue;
				Search_BelongTo(Begin_Mar,"b",Belong_Which_Mar);
				if(Is_Same_Species(Belong_Which_Mar))
					Register_Split_Process[i][17]=FALSE;
				else
				{
					if(Begin_Mar[17])
					{
						Insert_Split_Result(Begin_Mar,Belong_Which_Mar);
				    	temp = Mar_Num-2;
					}
			       	for(j=temp;j<=temp+1;j++)
			     	    Register_Split_Process[j][17]=FALSE;
				}
			}
		}
	}
}
/*
*  int Insert_Split_Result()函数是将分解后的集合插入到数组中.
*/
void Insert_Split_Result(int Begin_Mar[],int Belong_Which_Mar[])
{
	int i,Num;
	for(i=1;i<=Belong_Which_Mar[0];i++)
	{
		Num = Belong_Which_Mar[i] + Mar_Num;
		Register_Split_Process[Num][0]++;
		Register_Split_Process[Num][Register_Split_Process[Num][0]] = Begin_Mar[i];
		if(Register_Split_Process[Num][0]==1)
			Register_Split_Process[Num][17] = FALSE;
		else
			Register_Split_Process[Num][17] = TRUE;
	}
	Mar_Num += 2;
}
/*
*  void Initialization()函数是:初始化程序的变量等.
*/
void Initialization()
{
	int i=0;
	int A[Max_Marshal_Size+2],B[Max_Marshal_Size+2];

	for(;i<Max_State_Num;i++)
	{
		Register_Split_Process[i][0] = 0;
		Register_Split_Process[i][Max_Marshal_Size+1] = TRUE;
	}

	A[0] = 0,B[0] = 0;//B[Max_Marshal_Size+1] = TRUE;

	Find_A_B_Marshal(A,B);

	if(A[0] == 1||A[0] == 0)
		A[Max_Marshal_Size+1] = FALSE;
	else A[Max_Marshal_Size+1] = TRUE;
	if(B[0] == 1||B[0] == 0)
		B[Max_Marshal_Size+1] = FALSE;
	else A[Max_Marshal_Size+1] = TRUE;

	FuZhi(Register_Split_Process[0],A);
    FuZhi(Register_Split_Process[1],B);
}
/*
*  Search_SameKind()函数是查找集合找经过变换后那些属于
*  一类进而分成一组。
*/
void Search_BelongTo(int Begin_Mar[],char change[],int Belong_Which_Mar[])
{	
	int i,j,temp,be_i,be_j;

	Belong_Which_Mar[0] = 0;

	for(i=1;i<=Begin_Mar[0];i++)
	{
		for(j=0;j<read_num-1;j++)
			if(Begin_Mar[i]==READ[j].start&&strcmp(change,READ[j].ShiZi))
			{
				temp = READ[j].end;
				break;
			}
		Belong_Which_Mar[0] = Begin_Mar[0];
		for(be_i=0;be_i<Mar_Num;be_i++)
		{
			for(be_j=1;be_j<=Register_Split_Process[be_i][0];be_j++)
			{
				/* 找出对应位置上的状态经过change变换后属于那个集合 */
				if(Register_Split_Process[be_i][be_j] == temp)  
				{
                    Belong_Which_Mar[i] = be_i;
					break;
				}
			}
		}
	}
}
/*
*  Is_Same_Species()函数是:判断集合中的元素是否一样.
*  same return TRUE;or return FALSE;
*/
int Is_Same_Species(int Belong_Which_Mar[])
{
	int j;
	for(j=1;j<Belong_Which_Mar[0];j++)
	{
		if(Belong_Which_Mar[j]!=Belong_Which_Mar[j+1])
		{
			return FALSE;
		}
	}
	return TRUE;
}
/*
*  void Find_A_B_Marshal()函数是:
*  由State_dictionary里找最初的A和B集合
*/
void Find_A_B_Marshal(int A[],int B[])
{
	int i=0,j,flag = TRUE;
	for(;i<dictionary_num-1;i++)
	{
		flag = TRUE;
		for(j=1;j<=State_dictionary[i][0];j++)
			if(State_dictionary[i][j] == Y)
			{
				B[0] ++;
				B[B[0]] = i;
				flag = FALSE;
                break;
			}
		if(flag)
		{
			A[0] ++;
		    A[A[0]] = i;
		}
	}
}
/*
*  FuZhi()函数是:将一个数组赋值给另一个数组的操作.
*  具体的就是将Array2赋给Array1.
*/
void FuZhi(int Array1[],int Array2[])
{
	int i=0;
	for(;i<=Array2[0];i++)
	{
		Array1[i] = Array2[i];
	}
	Array1[17]=Array2[17];
}
/*
*  Read_from_File()函数是:将上一步的结果从文件中读入.
*  需要读入两个文件内容到READ[]数组中和State_dictionary[][]状态表
*/
void Read_from_File()
{
	FILE *fp;
    int j=0;
	Read  read;

    /* 打开文件"Confirm_NFA.txt"将其内容读到READ[]数组里 */
    if((fp=fopen("Confirm_NFA.txt","r"))==NULL)
    {
        printf("Cannot open file normally and strike any key exit!");
        getch();
        return;
    }
    while(!feof(fp))
    {
		fscanf(fp,"%d %s %d",&read.start,read.ShiZi,&read.end);
        READ[read_num] = read;
		read_num++;
    }
    fclose(fp);

	/* 打开文件"Confirm_NFA_NewState.txt"将其内容读到State_dictionary数组里 */
    if((fp=fopen("Confirm_NFA_NewState.txt","r"))==NULL)
    {
        printf("Cannot open file normally and strike any key exit!");
        getch();
        return;
    }
    while(!feof(fp))
    {
        for(j=0;j<=State_dictionary[dictionary_num][0];j++)
            fscanf(fp,"%d",&State_dictionary[dictionary_num][j]);
        dictionary_num ++;
    }
    fclose(fp);
}

/*
*  PrintInput()函数是打印读入的数据:
*  目的是看读到的数据是否有误
*/
void PrintInput()
{
	int i=0,j=0;
    
	printf("--------------状态字典内容:--------------\n");
    for(;i<dictionary_num-1;i++)
    {
        for(j=1;j<=State_dictionary[i][0];j++)
            printf("%d  ",State_dictionary[i][j]);
        printf("\n");
    }
    printf("\n--------------未化简DFA内容:--------------\n");
    for(i=0;i<read_num-1;i++)
    {
        printf("Start:%d\t\tInput:%s\t\tEnd:%d\n",
            READ[i].start,READ[i].ShiZi,READ[i].end);
    }
}