nfa2dfa.cpp

/// Write a program to implement nfa to dfa.

#include<iostream>
#include<cstdio>
#include<vector>
#include<fstream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<map>
#include<queue>
#define ll long long int
#define pp pair<int,int>
#define mpi make_pair
#define STATES 4
#define ALPHA 2
using namespace std;
int cnt=0;
int initial_state;
vector<int>final_states;
bool is_final[100];
bool check[100]={0};
vector<int>a[120]; vector<int>b[120]; vector<int>c[120];
map<vector<int>,int> mp;
map<int,vector<int> > rmp;
map<int,vector<int> > ::iterator rit;
map<vector<int>,int>::iterator iit;
map<int,int>mpa,mpb;
map<int,int>::iterator it;
int main(){
ifstream fin;
fin.open("input.txt",ifstream::in);
string s;

int k=0;
/// 3 input symbols
while(getline(fin,s)){
	//cout<<s<<endl;
	if(k==0){
		initial_state=s[0]-'0';
		k++;
		continue;
	}
	string ss,ts,us;
	int flag=0;
	for(int i=0; s[i];i++){
		if(s[i]==' ' && flag==0){
			flag=1;
		}
		else
		if(s[i]==' ' && flag==1) flag=2;
		if(!flag && s[i]!=' '){
		ss+=s[i];
		}
		if(flag==1 && s[i]!=' '){
		ts+=s[i];
		}
		if(flag==2 && s[i]!=' '){
		us+=s[i];
		}
	}
	if(k==1){
			for(int i=0;ss[i];i++){
		if(ss[i]==',') continue;
		int x;
		x=ss[i]-'0';
		final_states.push_back(x);
		is_final[x]=1;
	}
	k++;
	continue;
	}
	vector<int>tt;
	tt.push_back(cnt);
	mp.insert(make_pair(tt,cnt));
	rmp.insert(make_pair(cnt,tt));
		cnt++;
	//cout<<ss<<"="<<ts<<"="<<us<<endl;
	for(int i=0;ss[i];i++){
		if(ss[i]==',') continue;
		int x;
		x=ss[i]-'0';
		a[k-2].push_back(x);
	}
	for(int i=0;ts[i];i++){
		if(ts[i]==',') continue;
		int x;
		x=ts[i]-'0';
		b[k-2].push_back(x);
	}
	for(int i=0;us[i];i++){
		if(us[i]==',') continue;
		int x;
		x=us[i]-'0';
		c[k-2].push_back(x);
	}
	k++;
}
for(int i=0;i<k;i++){
		int f=0;
		vector<int>tt;
	for(int j=0;j<a[i].size();j++){
			if(is_final[a[i][j]]) f=1;
		//cout<<a[i][j]<<",";
		tt.push_back(a[i][j]);
	}
	if(!tt.empty()){
			iit=mp.find(tt);
			if(iit!=mp.end()){
				if(f) is_final[iit->second]=1;
				mpa.insert(make_pair(i,iit->second));
			}
			else{
				if(f) is_final[cnt]=1;
		mp.insert(make_pair(tt,cnt));
		rmp.insert(make_pair(cnt,tt));
		rmp.insert(make_pair(cnt,tt));
		mpa.insert(make_pair(i,cnt));
				cnt++;
			}
	}
	tt.clear();
	for(int j=0;j<b[i].size();j++){
		//cout<<b[i][j]<<",";
		tt.push_back(b[i][j]);
	}
	if(!tt.empty()){
	iit=mp.find(tt);

			if(iit!=mp.end()){
				if(f) is_final[iit->second]=1;
				mpb.insert(make_pair(i,iit->second));
			}
			else{
				if(f) is_final[cnt]=1;
		mp.insert(make_pair(tt,cnt));
		rmp.insert(make_pair(cnt,tt));
		mpb.insert(make_pair(i,cnt));
				cnt++;
			}
	}
}

for(it=mpa.begin();it!=mpa.end();it++){
	cout<<it->first<<","<<it->second<<" ";
}
printf("\n");
for(it=mpb.begin();it!=mpb.end();it++){
	cout<<it->first<<","<<it->second<<" ";
}
cout<<endl;

/*for(iit=mp.begin();iit!=mp.end();iit++){
		vector<int>t=iit->first;
for(int j=0;j<t.size();j++) cout<<t[j]<<" ";
	cout<<iit->second<<endl;
}*/
queue<int>Q;
Q.push(initial_state);

///start of an era

while(!Q.empty()){
	int flag=0;
	int top=Q.front();
	cout<<top<<endl;
	Q.pop();
	it=mpa.find(top);
	check[top]=1;
	if(it!=mpa.end()){
		flag=1;
		//printf("top=%d %d\n",top,it->second);
		if(!check[it->second])
		Q.push(it->second);
	}
	it=mpb.find(top);
	if(it!=mpb.end()){
		flag=1;
		if(!check[it->second])
		Q.push(it->second);
	}
	if(flag) continue;
	rit=rmp.find(top);
	vector<int>viv=rit->second;

	bool is[100]={0};
	for(int i=0;i<viv.size();i++){
		it=mpa.find(viv[i]);
		if(it!=mpa.end()){
			is[it->second]=1;
		}
	}
	flag=0;
	viv.clear();
	for(int i=0;i<100;i++){
		if(is[i]){
			viv.push_back(i);
			if(is_final[i]) flag=1;
		}
	}
	if(viv.size()>0){
		iit=mp.find(viv);
		rit=rmp.find(viv[0]);
		viv=rit->second;
		iit=mp.find(viv);
		if(iit!=mp.end()){
				if(!check[iit->second]) Q.push(iit->second);
			mpa.insert(make_pair(top,iit->second));
		}
		else{
				if(flag) is_final[cnt]=1;
			mp.insert(mpi(viv,cnt));
			//cout<<top<<"="<<cnt<<endl;
		if(!check[cnt]) Q.push(cnt);
			rmp.insert(mpi(cnt,viv));
			mpa.insert(make_pair(top,cnt));
			cnt++;
		}
	}

	for(int kk=0;kk<100;kk++) is[kk]=0;
	rit=rmp.find(top);
	viv=rit->second;
	for(int i=0;i<viv.size();i++){
		it=mpb.find(viv[i]);
		if(it!=mpb.end()){
			is[it->second]=1;
		}
	}
	flag=0;
	viv.clear();
	for(int i=0;i<100;i++){
		if(is[i]){
			//cout<<"i="<<i;
			viv.push_back(i);
			if(is_final[i]) flag=1;
		}
	}
	//printf("\n");
	if(viv.size()>0){
		rit=rmp.find(viv[0]);
		viv=rit->second;
		iit=mp.find(viv);
		if(iit!=mp.end()){
				//cout<<iit->second<<endl;
				if(!check[iit->second]) Q.push(iit->second);
			mpb.insert(make_pair(top,iit->second));
		}
		else{
				if(flag) is_final[cnt]=1;
			mp.insert(mpi(viv,cnt));
		if(!check[cnt]) Q.push(cnt);
			rmp.insert(mpi(cnt,viv));
			mpb.insert(make_pair(top,cnt));
			cnt++;
		}
	}

}
for(iit=mp.begin();iit!=mp.end();iit++){
		vector<int>t=iit->first;
for(int j=0;j<t.size();j++) cout<<t[j]<<" ";
	cout<<iit->second<<endl;
}
cout<<endl;
for(it=mpa.begin();it!=mpa.end();it++){
	cout<<it->first<< "=>"<<it->second<<endl;
}
cout<<endl;
for(it=mpb.begin();it!=mpb.end();it++){
	cout<<it->first<< "=>"<<it->second<<endl;
}
return 0;
}

input.txt
0
0,1
1,2
1,2
1,3
1,2