编译原理实验2 / NFA确定化和DFA最小化
程序员文章站
2024-02-13 08:59:52
...
项目地址：https://github.com/LinXiaoDe/Quary
实验要求
第一部分 NFA确定化
一、实验目的
学习和掌握将NFA转为DFA的子集构造法。
二、实验任务
（1）存储NFA与DFA；
（2）编程实现子集构造法将NFA转换成DFA。
三、实验内容
（1）确定NFA与DFA的存储格式。
要求为3个以上测试NFA准备好相应有限自动机的存储文件。（可利用实验一（二）的基础）
（2）用C或C++语言编写将NFA转换成DFA的子集构造法的程序。
（3）测试验证程序的正确性。
测试不易。可求出NFA与DFA的语言集合的某个子集（如长度小于某个N），再证实两个语言集合完全相同！
（4）测试用例参考：将下列语言用RE表示，再转换成NFA使用：
(a)以a开头和结尾的小字字母串；a (a|b|…|z)*a | a(b)不包含三个连续的b的，由字母a与b组成的字符串；( | b | bb) (a | ab | abb)*(c)(aa|b)*(a|bb)*
1.图的数据结构
在正式开始讲解算法之前，我先快速定义一些数据结构和函数。为方便管理，我将所有图相关的数据结构声明在global.h中，在global.cpp中定义它们。
- 存储状态图的数据结构
存储状态图十分简单，定义一个包含id和alpha转换条件字符的Node结构体即可很好的描述状态图的临接关系。
struct Node{
int id; //字节点编号
char alpha; //转换条件字符
Node(int ii=0,char aa=' '):id(ii),alpha(aa){}
};
extern vector<Node> stateGraph[maxn]; //状态图
extern vector<Node> minDFAGraph[maxn]; //最小化DFA状态图
- 保存状态集合数据结构
使用一个集合set保存状态，为了可以向集合中添加新的集合，使用vector<set<int>> stateSet结构保存状态集合
extern vector<set<int>> stateSet; //状态集合
- 状态转换表使用一个二维数组描述
- 字符列表使用数组描述
- 终结点状态使用数组描述
- 定义一些必要的整型数据
extern int stateList[maxn][maxn]; //状态转换表
extern char alphaList[maxn]; //转换字符列表
extern bool isEnd[maxn]; //是否为终点
extern int graphSize; //图大小
extern int minSize; //最小化DFA大小
extern int alphaSize; //字符集大小
2.构建图
构建图依赖文件流，一个典型的文件输入如下：
#读入图状态个数
4
#读入图中终止状态个数和终止状态
1
2
#读入图中字符集大小和字符
2
a b
#读入转换条件个数和转换条件
7
0 a 1
1 a 0
0 b 0
0 # 2
2 a 2
2 b 3
3 b 2
#图构建成功
相应的，构图函数如下：
void buildGraph(string filename){ //构建NFA状态图
string info;
ifstream in(filename); //读取文件
//读入图状态个数
in>>info;
cout<<info<<endl;
in>>graphSize;
//读入图中终止状态个数和终止状态
in>>info;
cout<<info<<endl;
int m,id;
in>>m;
for(int i=0;i<m;i++){
in>>id;
isEnd[id]=true;
}
//读入图中字符集大小和字符
in>>info;
cout<<info<<endl;
in>>alphaSize;
for(int i=0;i<alphaSize;i++){
in>>alphaList[i];
}
//读入转换条件个数和转换条件
in>>info;
cout<<info<<endl;
int num,from,to;
char s;
in>>num;
for(int i=0;i<num;i++){
in>>from>>s>>to;
stateGraph[from].push_back(Node(to,s));
}
// printStateGraph();
in>>info;
cout<<info<<endl;
}
如果你想通过命令行的形式构建图，可以这样定义一个入口main函数：
#include "global.h"
using namespace std;
int main(int argc, char * argv[]){
if(argc!=2) return 0;
//构图
buildGraph(argv[1]);
printStateGraph(graphSize,stateGraph);
return 0;
}
测试图是构建是否成功：
3.DFA确定化算法思想——子集法
算法思想——子集法：
不失一般性，设字母表只包含两个a和b，我们构造一张表:
（1）置第1行第1列为e-closure({X})求出这一列的Ia，Ib；
（2）然后，检查这两个Ia，Ib，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第1列上，求出每行第2，3列上的集合…
（3）重复上述过程，知道所有第2，3列子集全部出现在第一列为止
伪代码
/*NFA确定化*/
void deterNFA(int start){
初始化
cur.insert(startSet);
遍历状态集合，直到集合尾，期间不断更新状态集合
for(int i=0;i<stateSet.size();i++){
for(int j=0;j<alphaSize;j++){
求MoveTo集合
cur=getMoveTo(cur,alphaList[j]);
求e_closure
cur=get_eclosure(cur);
if(cur.size()>0){
判断当前集合是否在状态集合中
不存在则加入集合
stateSet.push_back(cur);
}
else 否则表示当前的状态无法扩展出节点，我们将无法扩展出的状态标记为-1
stateList[i][j+1]=-1;
}
}
遍历所有的集合并且重新记录终止状态
for(int i=0;i<stateSet.size();i++){
cur=stateSet[i];
如果当前集合包含终止状态，则将当前集合记录为终止集合
}
}
4.DFA确定化代码实现
代码实现
#include "global.h"
#include <queue>
#include<string.h>
/*计算I的eclosure集合*/
set<int> getMoveTo(set<int> I,char a){ //计算集合I经过a字符到达的集合，方法广度优先搜索
set<int> newSet;
for(set<int>::iterator it=I.begin();it!=I.end();it++)
{
int cur=*it;
for(int i=0;i<stateGraph[cur].size();i++)
{
int id=stateGraph[cur][i].id;
char alpha=stateGraph[cur][i].alpha;
if(alpha==a)
newSet.insert(id);
}
}
return newSet;
}
/*计算I的eclosure集合*/
set<int> get_eclosure(set<int> I){ //计算get_eclosure(I)集，方法广度优先搜索
//拓扑排序算法
bool visited[graphSize];
memset(visited,false,sizeof(visited));
set<int> newSet;
queue<int> Q; //辅助队列
for(set<int>::iterator it=I.begin();it!=I.end();it++) //将当前有待扩展的set，压入队列，并插入新的set集合
{
Q.push(*it);
newSet.insert(*it);
}
while(!Q.empty()) //队列每次弹出首位，并以首位进行扩展
{
int q=Q.front();
Q.pop(); //扩展以后弹出
for(int i=0;i<stateGraph[q].size();i++)
{
int id=stateGraph[q][i].id;
char alpha=stateGraph[q][i].alpha;
if(alpha=='#' && visited[id]==false)
{
newSet.insert(id);
Q.push(id);
visited[id]=true; //如果找到了，那么就加入新的set，并标记已访问
}
}
}
return newSet;
}
/*查找状态集合*/
int findState(set<int>st){
for(int i=0;i<stateSet.size();i++)
if(stateSet[i]==st) return i;
return -1;
}
/*NFA确定化*/
void deterNFA(int start){
//初始化
bool tempisEnd[maxn]={0};
set<int>cur;
cur.insert(start);
cur=get_eclosure(cur);
stateSet.push_back(cur); //加入初始集合
cout<<"初始集合"<<endl;
printSet(cur);
//遍历状态集合，直到集合尾，期间不断更新状态集合
for(int i=0;i<stateSet.size();i++){
stateList[i][0]=i; //当前被扩展状态
for(int j=0;j<alphaSize;j++){
cur=stateSet[i]; //当前要扩展的集合
//求MoveTo集合
cur=getMoveTo(cur,alphaList[j]);
//求e_closure
cur=get_eclosure(cur);
cout<<"eclurse: "<<i<<endl;
printSet(cur);
if(cur.size()>0){
//判断当前集合是否在状态集合中
int where=findState(cur);
//不存在则加入集合
if(where==-1){
stateSet.push_back(cur);
where=stateSet.size()-1;
}
stateList[i][j+1]=where;
}
else //否则表示当前的状态无法扩展出节点，我们将无法扩展出的状态标记为-1
stateList[i][j+1]=-1;
}
}
for(int i=0;i<stateSet.size();i++){
cur=stateSet[i];
//记录状态
for(set<int>::iterator it=cur.begin();it!=cur.end();it++){
if(isEnd[*it]) tempisEnd[i]=true;
}
}
memset(isEnd,false,sizeof(isEnd));
for(int i=0;i<stateSet.size();i++){
isEnd[i]=tempisEnd[i];
}
}
void buildDeterDFA(){ //根据状态表构建确定化后的DFA
for(int i=0;i<graphSize;i++)
stateGraph[i].clear();
graphSize=stateSet.size(); //更新图的规模
for(int i=0;i<stateSet.size();i++){
int parent=stateList[i][0]; //取出父节点
for(int j=1;j<=alphaSize;j++){
int id=stateList[i][j]; //状态编号
if(id!=-1){
char alpha=alphaList[j-1]; //转换条件
stateGraph[parent].push_back(Node(id,alpha));
}
}
}
}
测试
$ ./main sample/sample3.py
#读入图状态个数
#读入图中终止状态个数和终止状态
#读入图中字符集大小和字符
#读入转换条件个数和转换条件
#图构建成功
图构建成功
----------当前状态图----------
始末状态列表:
0:0
1:0
2:0
3:0
4:0
5:0
6:0
7:1
状态图:
0:# 5
1:a 3
1:b 4
2:# 6
3:a 2
4:b 2
5:a 5
5:b 5
5:# 1
6:a 6
6:b 6
6:# 7
------------------------------
初始集合
0 1 5
eclurse: 0
1 3 5
eclurse: 0
1 4 5
eclurse: 1
1 2 3 5 6 7
eclurse: 1
1 4 5
eclurse: 2
1 3 5
eclurse: 2
1 2 4 5 6 7
eclurse: 3
1 2 3 5 6 7
eclurse: 3
1 4 5 6 7
eclurse: 4
1 3 5 6 7
eclurse: 4
1 2 4 5 6 7
eclurse: 5
1 3 5 6 7
eclurse: 5
1 2 4 5 6 7
eclurse: 6
1 2 3 5 6 7
eclurse: 6
1 4 5 6 7
NFA确定化构建成功：
----------当前状态图----------
始末状态列表:
0:0
1:0
2:0
3:1
4:1
5:1
6:1
状态图:
0:a 1
0:b 2
1:a 3
1:b 2
2:a 1
2:b 4
3:a 3
3:b 5
4:a 6
4:b 4
5:a 6
5:b 4
6:a 3
6:b 5
- 构建出DFA结果如下：
第二部分 DFA最小化
一、实验目的
学会编程实现等价划分法最小化DFA。
二、实验任务
先完善DFA，再最小化DFA。
三、实验内容
（1）准备3个以上测试DFA文件。（提示：其中一定要有没有最小化的DFA）
（2）用C或C++语言编写用等价划分法最小化DFA的程序。
（3）经测试无误。测试不易。可求出两个DFA的语言集合的某个子集（如长度小于某个N），再证实两个语言集合完全相同！
1.DFA最小化思想——等价合并法
算法思想：子集法
- 将整个状态图视作不等价的状态集合，以此选择其中的等价对合并，直到不存在等价对的时候算法结束。
- 等价对的被定义为：
1.如果存在两种状态同为终止或非终止状态
2.且输入所有字符，到达的状态都一样，那么就等效，可以合并
3.优先保留有自旋的状态
伪代码如下：
void MinDFA(){
for(int k=0;k<graphSize-1;k++){
for(int i=0;i<graphSize;i++){
for(int j=0;j<graphSize;j++){
if(i!=j){
if(i j等价)合并他们 mergeState(j,i);
}
}
}
}
}
重构状态图
rebuildDFA();
}
2.DFA最小化代码实现
#include "global.h"
#include <map>
#include<string.h>
/*
判断两个状态是否等价,返回等价寻找结果
1.如果存在两种状态同为终止或非终止状态
2.且输入所有字符，到达的状态都一样，那么就等效，可以合并
3.优先保留有自旋的状态
*/
int findEqual(int u,int v){
//不同为等价状态或节点的边数不一样，不等价
if(isEnd[u]!=isEnd[v]||stateGraph[u].size()!=stateGraph[v].size()||stateGraph[u].size()==0)
return -1;
bool isEqual=false;
for(int i=0;i<stateGraph[u].size();i++){
int a=stateGraph[u][i].id;
int j;
for(j=0;j<stateGraph[v].size();j++){
int b=stateGraph[v][j].id;
if(a==b) break;
}
if(j==stateGraph[v].size()) return -1;
}
for(int i=0;i<stateGraph[u].size();i++) //判断是否有自旋
if(stateGraph[u][i].id==u)
return u;
return v;
}
/*合并两个状态，u，v->u*/
void mergeState(int u,int v){
cout<<"合并状态"<<u<<":"<<v<<endl;
stateGraph[v].clear();
for(int i=0;i<graphSize;i++){
for(int j=0;j<stateGraph[i].size();j++){
int cur=stateGraph[i][j].id;
//指向v状态的边指向u
if(cur==v)
stateGraph[i][j].id=u;
}
}
printStateGraph(graphSize,stateGraph);
}
//重新构建DFA，整合下标问题
void rebuildDFA(){
int empty=0;
map<int,int>reTable; //重定向表
minSize=graphSize;
for(int i=0;i<graphSize;i++){
if(stateGraph[i].size()==0){
minSize--;
empty++;
}
else
reTable.insert(map<int,int>::value_type(i,i-empty));
}
//排除状态
for(int i=0;i<graphSize;i++){
if(stateGraph[i].size()!=0){
int par=reTable[i];
for(int j=0;j<stateGraph[i].size();j++){
int id=stateGraph[i][j].id;
id=reTable[id]; //映射到新的下标
char alpha=stateGraph[i][j].alpha;
minDFAGraph[par].push_back(Node(id,alpha));
}
}
}
bool tempIsEnd[maxn]={0};
//重构终结集合
for(map<int,int>::iterator it=reTable.begin();it!=reTable.end();it++){
cout<<"it: "<<it->first<<it->second<<endl;
tempIsEnd[it->second]=isEnd[it->first];
}
memset(isEnd,false,sizeof(isEnd));
for(int i=0;i<minSize;i++){
isEnd[i]=tempIsEnd[i];
}
}
void MinDFA(){
//遍历所有的状态
for(int k=0;k<graphSize-1;k++){
for(int i=0;i<graphSize;i++){
for(int j=0;j<graphSize;j++){
if(i!=j){
//查找i，j状态是否等价
int u=findEqual(i,j);
if(u!=-1){
//合并两个等价状态
if(u==i) mergeState(i,j);
else mergeState(j,i);
}
}
}
}
}
// cout<<"打印DFA未重构最小化集合"<<endl;
// printStateGraph(graphSize,stateGraph);
//重构
rebuildDFA();
}
测试结果：
----------当前状态图----------
始末状态列表:
0:0
1:0
2:0
3:1
4:1
5:1
6:1
状态图:
0:a 1
0:b 2
1:a 3
1:b 2
2:a 1
2:b 4
3:a 3
3:b 5
4:a 6
4:b 4
5:a 6
5:b 4
6:a 3
6:b 5
------------------------------
合并状态3:6
----------当前状态图----------
始末状态列表:
0:0
1:0
2:0
3:1
4:1
5:1
6:1
状态图:
0:a 1
0:b 2
1:a 3
1:b 2
2:a 1
2:b 4
3:a 3
3:b 5
4:a 3
4:b 4
5:a 3
5:b 4
------------------------------
合并状态4:5
----------当前状态图----------
始末状态列表:
0:0
1:0
2:0
3:1
4:1
5:1
6:1
状态图:
0:a 1
0:b 2
1:a 3
1:b 2
2:a 1
2:b 4
3:a 3
3:b 4
4:a 3
4:b 4
------------------------------
合并状态3:4
----------当前状态图----------
始末状态列表:
0:0
1:0
2:0
3:1
4:1
5:1
6:1
状态图:
0:a 1
0:b 2
1:a 3
1:b 2
2:a 1
2:b 3
3:a 3
3:b 3
------------------------------
it: 00
it: 11
it: 22
it: 33
最小化的DFA构建成功：
----------当前状态图----------
始末状态列表:
0:0
1:0
2:0
3:1
状态图:
0:a 1
0:b 2
1:a 3
1:b 2
2:a 1
2:b 3
3:a 3
3:b 3
------------------------------
构建最小化DFA
上一篇： java配置dbcp连接池(数据库连接池)示例分享
下一篇： 如何修改php出错页面的颜色？