正文
dfa最小化，终于完成了。
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
采取的方法是hopcroft的填表法，详情见如下代码
#include "nfa_to_dfa.h"
int* dfa_diff_matrix; int mini_dfa_number;//这个是最小化的 dfa表的索引
typedef struct _min_dfa_node
{
pdfa_edge begin;
int is_end;//记录是否是接受节点
}min_dfa_node,*pmin_dfa_node;
min_dfa_node mini_dfa_table[];//设定为100，其实也可以malloc一下，因为我们已经知道了有多少个节点了
//为了偷懒，算了
is_diff(int input_a,int input_b)//判断两个点是不是等价的程序,注意我们传参数的时候默认a比b大
{
int destination_a,destination_b;//临时的转换目标地址
pdfa_edge temp_edge;//遍历邻接表
char label_traverse;//用来遍历符号表
int for_i;
for(for_i=;for_i<alpha_size;for_i++)
{
label_traverse=mini_alpha_set[for_i];
temp_edge=current_dfa_table[input_a].begin;
while(temp_edge!=NULL&&temp_edge->label!=label_traverse)
{
temp_edge=temp_edge->next;
}
if(temp_edge==NULL)
{
destination_a=;
}
else
{
destination_a=temp_edge->dest_dfa_index;
}
temp_edge=current_dfa_table[input_b].begin;
while(temp_edge!=NULL&&temp_edge->label!=label_traverse)
{
temp_edge=temp_edge->next;
}
if(temp_edge==NULL)
{
destination_b=;
}
else
{
destination_b=temp_edge->dest_dfa_index;
}
if(destination_a==destination_b)
{
//下一次吧
}
else
{
if(destination_a*destination_b==)
{
return ;
}
else
{
if( destination_a>destination_b)
{
if(dfa_diff_matrix[dfa_node_number*(input_a)+(input_b)]!=)//如果当前无法判别
{
if(is_diff(destination_a,destination_b))//如果可以判别
{
dfa_diff_matrix[dfa_node_number*(input_a)+(input_b)]=;
return ;
}
else
{
//继续判别
}
}
else
{
return ;
}
}
else
{
if(dfa_diff_matrix[dfa_node_number*(input_b)+(input_a)]!=)//如果当前无法判别
{
if(is_diff(destination_b,destination_a))//如果可以判别
{
dfa_diff_matrix[dfa_node_number*(input_b)+(input_a)]=;
return ;
}
else
{
//继续判别
}
}
else
{
return ;
}
}
}
}
}
return ;
}
void diff_matrix(void)
{
int already_diff_number;//这个是用来判断有多少个点已经经过了等价性测试
int for_i,for_j;
dfa_diff_matrix=malloc(sizeof(int)*dfa_node_number*dfa_node_number);//分配这个节点
for(for_i=;for_i<dfa_node_number;for_i++)
{
for(for_j=;for_j<dfa_node_number;for_j++)
{
dfa_diff_matrix[(for_i)*dfa_node_number+for_j]=;
}
}
for(for_i=;for_i<dfa_node_number;for_i++)
{
for(for_j=;for_j<for_i;for_j++)//这里首先根据是否是接受节点来初始化矩阵
{
if(current_dfa_table[for_i+].is_end!=current_dfa_table[for_j+].is_end)
{
dfa_diff_matrix[(for_i)*dfa_node_number+for_j]=;
}
}
}
do{
already_diff_number=;
for(for_i=;for_i<dfa_node_number;for_i++)
{
for(for_j=;for_j<for_i;for_j++)
{
if(dfa_diff_matrix[(for_i)*dfa_node_number+for_j]!=)
{
if(is_diff(for_i,for_j)==)
{
dfa_diff_matrix[(for_i)*dfa_node_number+for_j]=;
}
}
}
}
}while(already_diff_number!=);//如果本趟处理没有找到新的可分节点，就结束
for(for_i=;for_i<dfa_node_number;for_i++)
{
for(for_j=;for_j<dfa_node_number;for_j++)
{
printf("%d ",dfa_diff_matrix[(for_i)*dfa_node_number+for_j]);
}
printf("\n");
}
}
void minimize_dfa_matrix(void)//在已经构建好了dfa_diff_matrix后，开始群聚，并建图
{
//现在开始群聚
int* already_in_group;//用来记录哪些点已经在群里面了
int* temp_group;
int* before_min_access;//这里来标注哪些节点已经通过了最简化dfa的转换
int group_number=;//注意群号由0开始
int* index_of_group;
pdfa_edge temp_edge;//这个是用来重新建立最小化dfa的临时边
pdfa_edge temp_add_edge;//这个是用来往最小dfa里面增加边的临时边
int dest_group_number;//这个是在增加边的时候的目标编号
int **group_set;
int for_i,for_j;
group_set=malloc(sizeof(int)*dfa_node_number);
already_in_group=malloc(sizeof(int)*dfa_node_number);
for(for_i=;for_i<dfa_node_number;for_i++)
{
already_in_group[for_i]=;
*(group_set+for_i)=NULL;
}
for(for_i=;for_i<dfa_node_number-;for_i++)//聚集
{
if(already_in_group[for_i]==)
{
already_in_group[for_i]=;
temp_group=malloc(sizeof(int)*dfa_node_number);
*(group_set+group_number++)=temp_group;
for(for_j=;for_j<dfa_node_number;for_j++)
{
temp_group[for_j]=;
}//注意这里也需要考虑加减1的问题
temp_group[for_i]=;
for(for_j=for_i+;for_j<dfa_node_number;for_j++)
{
if(!dfa_diff_matrix[(for_j)*dfa_node_number+for_i])
{
temp_group[for_j]=;
already_in_group[for_j]=;
}
}
}
}//现在已经完全都聚集为一团了
mini_dfa_number=group_number;
//现在再将节点和群的关系反转
index_of_group=malloc(sizeof(int)*dfa_node_number);
//这里又需要注意加减1的关系，由于这里dfa节点是从1标号的，而我们在index_of_group是从0标号的，要注意
for(for_i=;for_i<dfa_node_number;for_i++)
{
index_of_group[for_i]=;
}
for_i=;
while(*(group_set+for_i)!=NULL)//前面开了一个索引数组，现在来赋值，这样就可以直接得到某个节点所在的群号
{
for(for_j=;for_j<dfa_node_number;for_j++)
{
if(*(*(group_set+for_i)+for_j)==)
{
index_of_group[for_j]=for_i;
}
}
for_i++;
}//现在关系已经翻转了
//下一步就是利用这个点与群的关系来新建立一个dfa图
//这里的群号就是节点的编号，由于每个群里面的节点都是等价的，所以只需要找一个节点就行了
for(for_i=;for_i<=group_number;for_i++)//这里的for_i是用来表示最小dfa图的标号，所以从1开始
{
//对每一个群进行遍历
mini_dfa_table[for_i].begin=NULL;
mini_dfa_table[for_i].is_end=;
for_j=;
while(*(*(group_set+for_i-)+for_j)!=)//由于group是从0开始标号的，所以要减去1
{
for_j++;
}//找到这个群里面一个节点,注意加减一问题，少犯错误啊，1号节点存储在0号位置上
if(current_dfa_table[for_j+].is_end)
{
mini_dfa_table[for_i].is_end=;//标记为结束节点
}
temp_edge=current_dfa_table[for_j+].begin;
while(temp_edge!=NULL)//重新建设邻接表
{
temp_add_edge=malloc(sizeof(struct _dfa_edge));
temp_add_edge->label=temp_edge->label;
temp_add_edge->next=mini_dfa_table[for_i].begin;
dest_group_number=index_of_group[temp_edge->dest_dfa_index-]+;//特别要注意这里的加一和减一
//由于temp_edge->dest_dfa_node是从1开始标号的，而index_of_group是从0开始标号的，所以我们要减一
//同样，又由于最后的最简化dfa的图是从1开始标号的，所以我们要加1;
temp_add_edge->dest_dfa_index=dest_group_number;
mini_dfa_table[for_i].begin=temp_add_edge;
temp_edge=temp_edge->next;
}
//本群的邻接表构建完成
}//所有群的邻接表构建完成
}
void show_mini_dfa(void)//输出图
{
int for_i;
pdfa_edge temp_dfa_edge;
number_of_end_dfa=;
for(for_i=;for_i<=mini_dfa_number;for_i++)
{
if(mini_dfa_table[for_i].is_end==)
{
printf("this node is an destination node ,index is %d\n",for_i);
}
temp_dfa_edge=mini_dfa_table[for_i].begin;
while(temp_dfa_edge!=NULL)
{
printf("there is an dfa edge from %d to %d with label %c\n",for_i,temp_dfa_edge->dest_dfa_index,temp_dfa_edge->label);
temp_dfa_edge=temp_dfa_edge->next;
}
}
printf("the minimized dfa is completed\n");
}
