【编译原理实验】Lab2(二)DFA最小化
程序员文章站
2024-02-13 10:16:58
...
一、实验目的
学会编程实现等价划分法最小化DFA。
二、实验任务
先完善DFA,再最小化DFA。
三、实验内容
(1)准备3个以上测试DFA文件。(提示:其中一定要有没有最小化的DFA)
(2)用C或C++语言编写用等价划分法最小化DFA的程序。
(3)经测试无误。测试不易。可求出两个DFA的语言集合的某个子集(如长度小于某个N),再证实两个语言集合完全相同!
四、实验步骤
如何存DFA
用到实验的第一部分DFA确定化,存节点集和边集
状态集还是用一个整数来表示,二进制位表示是否包含某个状态。
Hopcroft算法思想
简简单单一句基于等价类的思想,很泛的概念。说起等价类,那得追溯到离散数学了。但是就写这个算法而言,没必要。
个人一些简单的理解:DFA中的状态q0,q1,做一个q0-q1映射,根据DFA边集画出状态图,不看状态标号,状态图仍然一样的。那说明q0和q1可以合并。也就是所谓的等价。
算法伪代码
算法步骤
首先把所有节点分为N和A两个集合,集非结束态和结束态
S = {N,A},然后遍历所有字符,去看每个字符都否对S中的状态集进行划分,每轮遍历下来,如果S仍然在扩大,则从头再来一轮。直到S不再扩大,即没有状态集可分为止。
此实验最核心的应该就是c can split s
这里s指的是S中的一个状态集
1.遍历s中每个状态,记录每个状态吃了字符c之后到达的状态,吃不了的不管。
2.把到达的状态分类,分类依据:把属于同一个状态集的合在一起。这里的同一个状态集指的是S中现在有的状态集。
3.按照第二步的分法把s分割。注意:
是从s中分割出去,s最后保留下来的是吃了字符c还在状态集s中的状态或者吃不了c字符的状态。
由于每个状态都属于某个状态集,所以定义一个全局数组p,p[i] = x
表示i这个状态属于状态集x。
算法代码
注释很详细,不再过多赘述
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <set>
#include <cstring>
using namespace std;
int zf;
char zfj[101];
struct Node{//NFA节点
int s;
bool flag;//标记一个DFA节点集合是否包含NFA结束态,即表示DFA中是否是一个结束态
Node(int ss,bool f){
s = ss;
flag = f;
}
};
struct Edge{//DFA边
int to;
char c;
Edge(int y,char z){
to = y;
c = z;
}
};
struct Edge_dfa{//存最小化DFA边集
int from;
int to;
char c;
Edge_dfa(int x,int y,char z){
from = x;
to = y;
c = z;
}
};
bool operator<(const Edge_dfa & x,const Edge_dfa & y)
{
if(x.from<y.from)
return true;
else if(x.to<y.to)
return true;
else return x.c < y.c;
}
vector<Node> V;//DFA节点集
vector<Edge> edge[101];//DFA边集
int v,e;
int t = 2;//默认可分为N和A
vector<int> eq;
set<Edge_dfa> Ed;
int p[101]; //记录状态属于哪个集合
void split(int x,char c)
{
int s = eq[x];
int a[101];//吃完字符达到的状态集
int b[101];//对应a中分割的吃字符前的状态
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
int i,j,k;
for(i = 0;i < v;i++){
if((s>>i)&1){//遍历集合中的状态
for(j = 0;j < edge[i].size();j++){
if(edge[i][j].c == c){
int v = edge[i][j].to;
a[p[v]] |= (1<<v);
b[p[v]] |= (1<<i);
}
}
}
}
int ll = t;
for(i = 0;i < ll;i++){
if(b[i]==eq[x]) break;
if(a[i] && i!=x){
eq.push_back(b[i]);
for(k = 0;k < v;k++)
if((b[i]>>k)&1)
p[k] = t;
eq[x]&=(~b[i]);
t++;
}
}
}
void Hopcroft()
{
int N = 0,A = 0;
for(int i = 0;i < v;i++){//分成N和A两个集合
if(V[i].flag){
A |= (1<<V[i].s);
p[V[i].s] = 1;
}
else{
N |= (1 << V[i].s);
p[V[i].s] = 0;
}
}
if(N = 0){
printf("全部状态合并为一个状态");
return ;
}
eq.push_back(N);
eq.push_back(A);
int i,j;
int l;
while(1){
for(i = 0;i < zf;i++){
l = t;
for(j = 0;j < l;j++)
split(j,zfj[i]);
}
if(l==t) break;//集合大小不变算法结束
}
}
void put_status(int x,int i)
{
int j;
printf("状态:");
for(int j = 0;j < v;j++)
if((x>>j)&1)
printf("q%d ",j);
printf("可合并,记作状态T%d\n",i);
}
int main()
{
ifstream in("dfa_3.txt");
int x,y;
char z;
in >> zf;
for(int i = 0;i < zf;i++)
in >> zfj[i];
in >> v;
for(int i = 0;i < v;i++){
bool flag = false;
in >> x >> y;
if(y == 1) flag= true;
V.push_back(Node(x,flag));
}
in >> e;
for(int i = 0;i < e;i++){
in >> x >> y >> z;
edge[x].push_back(Edge(y,z));
}
Hopcroft();
for(int i = 0;i < t;i++)
put_status(eq[i],i);
for(int i = 0;i < v;i++)//合并边集
for(int j = 0;j < edge[i].size();j++)
Ed.insert(Edge_dfa(p[i],p[edge[i][j].to],edge[i][j].c));
for(set<Edge_dfa>::iterator it=Ed.begin() ;it!=Ed.end();it++)
printf("状态T%d -> 状态T%d,吃入字符%c\n",(*it).from,(*it).to,(*it).c);
in.close();
return 0;
}
运行结果
测试样例1:
测试样例2:
2
a b
8
0 1
1 1
2 1
3 1
4 0
5 1
6 1
7 1
15
0 1 a
0 2 b
1 3 a
1 4 b
2 1 a
2 5 b
3 1 a
3 2 b
4 6 b
5 1 a
5 5 b
6 7 a
6 4 b
7 7 a
7 4 b