HUNAN UNIVERSITY
计算理论导引实验报告
题目：NFA转换为DFA 学生姓名：
学生学号：
专业班级：计算机科学与技术
上课老师：
实验日期：
一、实验目的 (2)
二、实验方法.......................................................................................... 错误！未定义书签。
三、实验代码.......................................................................................... 错误！未定义书签。
四、测试数据以及运行结果 (5)
一、实验目的
?将一个给定的NFA转换为一个完全等价的DFA。
二、实验方法
编写一个算法/程序，将一个给定的NFA转换为一个完全等价的DFA 三、实验代码
#include
#include
#include
#include
#include
using namespace std;
int ans[65536];
int one[65536];
int zero[65536];
int lft[65536];
int rgt[65536];
int change[65536];
bool vis[65536];
bool ac[65536];
int cnt, n, q, f;
void init()
{
}
int getlow(int p)
{
return p&(-p);
}
int getloc(int p)
{
int x = 1;
if(p == 1)
return 0;
int i = 0;
while(++i)
{
x <<= 1;
if(p == x)
return i;
}
return 0;
}
int mege(int a, int b)
{
while(b)
{
int x = getlow(b);
if(!(a&x))
a ^= x;
b ^= x;
}
return a;
}
void dfs(int p)
{
ans[cnt] = p;
int lsum = 0, rsum = 0;
while(p)
{
int x = getlow(p);
int y = getloc(x);
lsum = mege(lsum, zero[y]);
rsum = mege(rsum, one[y]);
p ^= x;
}
lft[cnt] = lsum;
rgt[cnt] = rsum;
cnt++;
if(!vis[lsum])
vis[lsum] = 1, dfs(lsum);
if(!vis[rsum])
vis[rsum] = 1, dfs(rsum);
}
int main()
{
init();
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d%d%d", &n, &q, &f);
for(int i = 0; i < n; i++)
scanf("%d", &zero[i]);
for(int i = 0; i < n; i++)
scanf("%d", &one[i]);
cnt = 0;
memset(vis, 0, sizeof(vis));
memset(ac, 0, sizeof(ac));
vis[q] = 1;
dfs(q);
int sum = 0;
for(int i = 0; i < cnt; i++)
if(ans[i]&f)
ac[i] = 1, sum++;
for(int i = 0; i < cnt; i++)
change[ans[i]] = i;
printf("%d %d %d\n", cnt, sum, 0);
for(int i = 0, j = 0; i < cnt; i++)
{
if(ac[i])
{
if(j)
printf(" ");
printf("%d", i);
j++;
}
}
printf("\n");
for(int i = 0; i < cnt; i++)
{
if(i)
printf(" ");
printf("%d", change[lft[i]]);
}
printf("\n");
for(int i = 0; i < cnt; i++)
{
if(i)
printf(" ");
printf("%d", change[rgt[i]]);
}
printf("\n");
}
return 0;
}
四、测试数据以及运行结果
给出NFA，测试正确结果不唯一：
1
4 1 8
1 4 0 8
7 8 8 8
结论：NFA转换成DFA成功，该程序能实现NFA到DFA的转换