NFA确定化（C++实现）
NFA确定化
⽬录
⼀、确定化算法——⼦集法
⼦集法伪代码
void deterDFA(T){
给T加标记，说明T要作为出发状态去查输⼊符号的CLOSURE
对于状态集合T，在输⼊符号为x下，跳转到的状态集合U
for(对于任意⼀个输⼊符号a){
U =closure_T(move(T,a));
if(U不在Dstate状态集合中){
if(U包含NFA中的接受状态){
将U设置为接受状态
}
将U加⼊DFA的状态集合，DFA状态数⽬加1
}
对当前状态T和输⼊符号a构造状态转换到达状态U
}
}
⼆、函数说明
1. void BuildGraph(string filename);
通过读⼊txt⽂件filename构建NFA的状态转换图；
读⼊格式详见“Graph – 说明.txt”。
其中，状态转换图中的边存储在Edge[i]中（type(Edge[i]) = pair<int, char>），i表⽰边的起点，pair中的int表⽰边的终点，pair中的char表⽰转换字符。
2. void add(int a, int b, char signal);
a, b, signal分别表⽰边的起点、终点、转换字符。
3. int findState(set a);
在总状态集合中查是否存在状态集合a，如果存在则返回1，否则返回-1，即需要将该状态集合加⼊到总状态集合中。
4. set Graph::getClosure(set cur, char signal)
以cur为当前状态集合，寻转换字符为signal的Closure。
5. set Graph::getClosure(set cur)
以cur为当前状态集合，寻其ε-Closure。
6. set Graph::getClosure(int cur)
以cur为当前状态点，寻其ε-Closure。
三、实现代码
1.Graph.h
#ifndef GRAPH_H
#define GRAPH_H
#include<cstring>
#include<iostream>
#include<fstream>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int N =100;
class Graph
{
public:
//集合序号
char index;
//状态数量
int StateNum;
//初始点数量、终⽌点数量
int StartNum, StopNum;
//转换函数数量，字符集⼤⼩
int TransNum, LetterSize;
//终⽌状态集合，初始状态集合
int StopState[N], StartState[N];
//字符集合
char LetterSet[N];
//状态集合
set< pair<char, set<int>>> stateSet;
//状态队列
queue< set<int>> stateQueue;
/
/当前状态集合
set<int> currentState;
//转换集合
vector<pair<int,char>> Edge[N];
Graph();
//建图
void BuildGraph(string filename);
//添加转换条件
void add(int a,int b,char signal);
//NFA确定化
void deterDFA(int start);
/
/状态查函数
int findState(set<int>);
//重载求闭包函数
set<int>getClosure(int cur);
set<int>getClosure(set<int> cur);
set<int>getClosure(set<int> cur,char signal); //展⽰结果
void showDFA();
protected:
};
#endif
2.Graph.cpp
#include"Graph.h"
using namespace std;
Graph::Graph()
{
//从A开始编状态集合名称
index ='A';
}
void Graph::BuildGraph(string filename)
{
ifstream in(filename);
//读⼊状态数量
in>>StateNum;
cout<<"StateNum:"<<StateNum<<endl;
//读⼊终⽌状态
in>>StopNum;
for(int i=0; i<StopNum; i++)
{
in>>StopState[i];
}
cout<<"StopNum:"<<StopNum<<endl;
cout<<"StopState:";
for(int i=0; i<StopNum; i++)
{
cout<<StopState[i]<<' ';
}
cout<<endl;
//读⼊字符集合
in>>LetterSize;
for(int i=0; i<LetterSize; i++)
{
in>>LetterSet[i];
}
cout<<"LetterSize:"<<LetterSize<<endl;
cout<<"LetterSet:";
for(int i=0; i<LetterSize; i++)
{
cout<<LetterSet[i]<<' ';
}
cout<<endl;
//读⼊转换函数
in>>TransNum;
for(int i=0; i<TransNum; i++)
{
int a, b;
char w;
in>>a>>w>>b;
add(a, b, w);
}
cout<<"TransNum:"<<TransNum<<endl;
cout<<"Trans:"<<endl;
for(int i=0; i<StateNum; i++)
{
if(Edge[i].size()==0)continue;
for(auto k:Edge[i])
{
cout<<i<<' '<<k.second<<' '<<k.first<<endl; }
}
}
//a代表起点，b代表终点，signal代表对应字符void Graph::add(int a,int b,char signal)
{
Edge[a].push_back({b, signal});
}
//查状态集中是否有当前状态
int Graph::findState(set<int> cur)
{
for(auto k:stateSet)
{
if(k.second == cur)
return1;
}
return-1;
}
//求状态集合为cur，字符为signal的Closure
set<int> Graph::getClosure(set<int> cur,char signal)
{
set<int> newset;
for(set<int>::iterator it = cur.begin(); it != d(); it++)
{
for(auto k:Edge[*it])
{
//cout<<k.first<<' '<<k.second<<endl;
if(k.second == signal)
{
newset.insert(k.first);
//cout<<k.first<<endl;
}
}
}
return newset;
}
//求状态集合为cur的ε-Closure ('#'表⽰ε弧)
set<int> Graph::getClosure(set<int> cur)
{
set<int> newset = cur;
queue<int> q;
for(set<int>::iterator it = cur.begin(); it != d(); it++)
q.push(*it);
while(q.size())
{
int t = q.front();
q.pop();
set<int> newele =getClosure(t);
for(set<int>::iterator it = newele.begin(); it != d(); it++) {
q.push(*it);
newset.insert(*it);
}
}
return newset;
}
//求状态只有cur的ε-Closure
set<int> Graph::getClosure(int cur)
{
set<int> newset;
for(auto k:Edge[cur])
{
if(k.second =='#')
newset.insert(k.first);
}
return newset;
}
//NFA确定化
void Graph::deterDFA(int start)
{
//将初始状态加到当前状态集合
currentState.insert(start);
//求ε-Closure得到I
currentState =getClosure(currentState);
//将I加到状态集合和队列
stateSet.insert({index, currentState});
stateQueue.push(currentState);
cout<<"----------------------------------"<<endl;
cout<<" I Ia Ib"<<endl;
cout<<"----------------------------------"<<endl;
//当状态集合队列不为空
while(stateQueue.size())
{
//取队头状态集合并弹出，依次求其I,Ia和Ib
auto temp = stateQueue.front();
for(auto k:stateSet)
{
if(k.second == temp)
cout<<" "<<k.first;
}
stateQueue.pop();
//求Ia, Ib ...
for(int j=0; j<LetterSize; j++)
{
currentState = temp;
//先求对应字符的Closure
currentState =getClosure(temp, LetterSet[j]);
cstring转为int//再求该Closure的ε-Closure
currentState =getClosure(currentState);
if(currentState.size()>0)
{
if(findState(currentState)==-1)
{
//若求得的状态集合没有出现在总的状态集合和队列中，则加⼊ stateSet.insert({++index, currentState});
stateQueue.push(currentState);
}
for(auto k:stateSet)
{
//取出该状态集合对应的字母名称
if(k.second == currentState)
cout<<"\t\t"<<k.first;
}
}
}
cout<<endl;
}
cout<<"----------------------------------"<<endl;
}
void Graph::showDFA()
{
for(auto k:stateSet)
{
char id = k.first;
auto state = k.second;
cout<<id<<' ';
for(set<int>::iterator it = state.begin(); it != d(); it++)
cout<<*it<<' ';
cout<<endl;
}
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论