功能： 采用子集构造算法实现NFA的确定化
输入：读取NFA的文件(文件名test.txt), 文件格式：
第一列表示状态名，第二列和第三列分别表示输入字符a和b到达的状态
输出：确定化后的DFA(文件名为output.txt),格式如下：
第一列表示输入状态名，第二列表示重新命名的状态名，第三列和第四列分别表示输入字符a和b所到达的状态
代码：
#include <stdio.h>
#include <string.h>
/* 子集构造算法实现NFA的确定化
* 输入文件：test.txt的内容
* 状态名 输字符a到达的状态 字符b到达的状态
* 0 {0,1} {0,2}
* 1 {f} {NULL}
* 2 {NULL} {f}
* f {f} {f}
* 输出文件:out.test的内容（输入状态名，字符a到达的状态，字符b到达的状态）
* {0,}ABC
* {0,2,}CBD
* {0,2,f,}DED
* {0,1,f,}EED
* {0,1,}BEC
*
*@author： finch
*@time ： 2017-4-29
*/
#define num 10 //状态集合大小
#define stack_Size 10 //栈的大小
][]; //Dstates
/*
NFA信息表
*/
struct nfa_info
{
char c;
char a[num];
char b[num];
}nfa[num];
/*
DFA信息表
*/
struct dfa
{
char c[num];
char a[num];
char b[num];
}dfa[num];
/*
栈：用于实现未标记的状态的存储
可以用Dstates替代
*/
struct stack_info
{
char data[stack_Size][stack_Size];
int top;
};
typedef stack_info stack;
/*
栈的 初始化
*/
void initStack(stack *S)
{
S->top = -; // -1空栈
}
/*
栈是否为空
是： 返回 1
否： 返回 0
*/
int IsEmpty(stack *S)
{
)
{
;
}
else {
;
}
}
/*
将字符串 str入栈
*/
int push(stack *S, char str[])
{
S->top++;
if (S->top >= stack_Size)
{
printf("the stack is full\n");
;
}
strcpy(S->data[S->top], str);
printf("\n%d-%s\n", S->top, S->data[S->top]);
;
}
/*
栈顶元素出栈
赋值给str
*/
int pop(stack *S, char str[]) //出栈
{
)
{
printf("\nthe stack is empty\n");
;
}
strcpy(str, S->data[S->top]);
; i < num; i++)
{
S->data[S->top][i] = '\0';
}
S->top--;
;
}
/*
U是否在Dstates中
在：返回1
否：返回0
*/
int isBiaoji(char U[])
{
;
; Dstates[i][] != '\0';i++)
{
== strcmp(U, Dstates[i]))
state = ;
}
return state;
}
/*
是否属于NFA
*/
int isElem(char ch)
{
') || (ch >= 'A'&&ch <= 'Z'))
;
else
;
}
/*
从文件中读取数据并存到NFA中
*/
void input() //输入
{
FILE *fp_in;
fp_in = fopen("test.txt", "r");
if (fp_in == NULL)
{
printf("Error\n");
}
else {
char c;
; //行数
;
;
c = fgetc(fp_in);
while (c != EOF) //文件结束标志
{
if (c == '\n')
{
i++;
printf("\n");
j = ;
}
else if (c == '{') //遇见左括号，新的字符串
{
j++; //状态+1
index = ; //新的集合
}
)
{
) //state
{
nfa[i].c = c;
printf("C:%c\t", nfa[i].c);
}
) //经过a边到达的点
{
nfa[i].a[index] = c;
printf("A:%c\t", nfa[i].a[index]);
index++;
}
else //经过b边到达的点
{
nfa[i].b[index] = c;
printf("B:%c\t", nfa[i].b[index]);
index++;
}
}
else
{
;
}
c = fgetc(fp_in);
}
fclose(fp_in);
}
}
/*
将字符串str2中独有
的字符放到str1中
@time：2017-4-23
*/
void strcatIgnorReat(char str1[], char str2[])
{
];
; i < ;i++)
{
x[i] = '\0';
}
) //str1为空 ，直接连接
{
strcat(str1, str2);
}
else
{
strcpy(x, str2);
; str1[i] != '\0';i++)
{
; x[j] != '\0';j++)
{
if (str1[i] == x[j])
{
x[j] = '#'; //相同的用#替代
}
}
}
;i < strlen(x);i++)
{
if (x[i] != '#')
{
int index = strlen(str1);
str1[index] = x[i];
}
}
}
}
/*
状态c经过输入符号a上的转换可以到达
的NFA状态集合nfa_set
@time: 2017/4/23
@finch
*/
int move(char c, int a, char nfa_set[])
{
;
while (nfa[i].c != c && nfa[i].c != '\0') //状态c在NFA中的位置
{
i++;
}
if (nfa[i].c == c)
{
) //a边
{
!= strcmp("NULL", nfa[i].a))
{
strcatIgnorReat(nfa_set, nfa[i].a); //经过a可以到达的NFA状态集合
}
}
else {
!= strcmp("NULL", nfa[i].b)) //b边
strcatIgnorReat(nfa_set, nfa[i].b); //经过b可以到达的NFA状态集合
}
;
}
else {
;
}
}
/*
NFA确定化函数
从NFA状态Set开始可以转换
@time 2017/4/22
@finch
*/
void turn(char Set[], stack *S) //NFA确定化函数
{
; //标记数量
; //DFA下标
push(S, Set); //Set入栈
]; //每个集合经过的所有点的集合
strcpy(Dstates[bj_num], Set);
bj_num++;
== IsEmpty(S)) //栈不为空
{
char U[num]; //缓存
pop(S, U); //元素出栈
index++;
strcpy(dfa[index].c, U); //DFA
;a != ;a++) //分别对a，b边遍历
{
; i < ;i++)
{
buff[i] = '\0'; //清空
}
; U[i] != '\0'&&i < num; i++) //遍历str集合
{
move(U[i], a, buff);
}
)
{
strcpy(dfa[index].a, buff); //结合str在a边上的集合
}
else
{
strcpy(dfa[index].b, buff); //结合str在b边上的集合
}
== isBiaoji(buff))&&(strlen(buff)!=)) //新的非空集合未标记入栈并标记
{
push(S, buff);
strcpy(Dstates[bj_num], buff);
bj_num++;
}
}
}
}
/*
打印
@time 2017/4/23
*/
void print()
{
printf("\n\n");
; dfa[i].c[] != '\0';i++)
{
printf("<%s>\t\t<%s>\t\t<%s>\n", dfa[i].c, dfa[i].a, dfa[i].b);
}
}
/*
返回set在Dstates中的位置
返回 -1： 不存在
*/
int getIndex(char set[])
{
;
; Dstates[i][] != '\0';i++)
{
== strcmp(set, Dstates[i]))
state = i;
}
return state;
}
/*
输出
@time 2017/4/23
@finch
*/
void output()
{
FILE *fp_out = NULL;
if ((fp_out = fopen("output.txt", "w+")) == NULL)
{
printf("Error:can't open the file !");
}
else {
; dfa[i].c[] != '\0';i++) //重命名
{
fprintf(fp_out, "{", dfa[i].c);
; dfa[i].c[j] != '\0';j++)
{
fprintf(fp_out, "%c,", dfa[i].c[j]);
}
fprintf(fp_out, "}", dfa[i].c);
fprintf(fp_out, "%c", 'A' + getIndex(dfa[i].c));
== getIndex(dfa[i].a)) //符号a上的集合为空
{
fprintf(fp_out, "\t{%s}", "NULL");
}
else {
fprintf(fp_out, "\t%c", 'A' + getIndex(dfa[i].a));
}
== getIndex(dfa[i].b)) //符号b上的集合为空
{
fprintf(fp_out, "\t{%s}", "NULL");
}
else {
fprintf(fp_out, "\t%c", 'A' + getIndex(dfa[i].b));
}
fprintf(fp_out, "\n");
}
}
fclose(fp_out);
}
int main()
{
stack S;
initStack(&S);
input();
turn(", &S);
print();
output();
;
}