#include<iostream>
#include<bits/stdc++.h>
using namespace std;
void print(vector<vector<vector<int> > > table){
cout<<" STATE/INPUT |";
char a='a';
for(int i=0;i<table[0].size()-1;i++){
cout<<" "<<a++<<" |";
}
cout<<" ^ "<<endl<<endl;
for(int i=0;i<table.size();i++){
cout<<" "<<i<<" ";
for(int j=0;j<table[i].size();j++){
cout<<" | ";
for(int k=0;k<table[i][j].size();k++){
cout<<table[i][j][k]<<" ";
}
}
cout<<endl;
}
}
void printdfa(vector<vector<int> > states, vector<vector<vector<int> > > dfa){
cout<<" STATE/INPUT ";
char a='a';
for(int i=0;i<dfa[0].size();i++){
cout<<"| "<<a++<<" ";
}
cout<<endl;
for(int i=0;i<states.size();i++){
cout<<"{ ";
for(int h=0;h<states[i].size();h++)
cout<<states[i][h]<<" ";
if(states[i].empty()){
cout<<"^ ";
}
cout<<"} ";
for(int j=0;j<dfa[i].size();j++){
cout<<" | ";
for(int k=0;k<dfa[i][j].size();k++){
cout<<dfa[i][j][k]<<" ";
}
if(dfa[i][j].empty()){
cout<<"^ ";
}
}
cout<<endl;
}
}
vector<int> closure(int s,vector<vector<vector<int> > > v){
vector<int> t;
queue<int> q;
t.push_back(s);
int a=v[s][v[s].size()-1].size();
for(int i=0;i<a;i++){
t.push_back(v[s][v[s].size()-1][i]);
//cout<<"t[i]"<<t[i]<<endl;
q.push(t[i]);
}
while(!q.empty()){
int f=q.front();
q.pop();
if(!v[f][v[f].size()-1].empty()){
int u=v[f][v[f].size()-1].size();
for(int i=0;i<u;i++){
int y=v[f][v[f].size()-1][i];
if(find(t.begin(),t.end(),y)==t.end()){
//cout<<"y"<<y<<endl;
t.push_back(y);
q.push(y);
}
}
}
}
return t;
}
int main(){
int n,alpha;
cout<<"************************* NFA to DFA *************************"<<endl<<endl;
cout<<"Enter total number of states in NFA : ";
cin>>n;
cout<<"Enter number of elements in alphabet : ";
cin>>alpha;
vector<vector<vector<int> > > table;
for(int i=0;i<n;i++){
cout<<"For state "<<i<<endl;
vector< vector< int > > v;
char a='a';
int y,yn;
for(int j=0;j<alpha;j++){
vector<int> t;
cout<<"Enter no. of output states for input "<<a++<<" : ";
cin>>yn;
cout<<"Enter output states :"<<endl;
for(int k=0;k<yn;k++){
cin>>y;
t.push_back(y);
}
v.push_back(t);
}
vector<int> t;
cout<<"Enter no. of output states for input ^ : ";
cin>>yn;
cout<<"Enter output states :"<<endl;
for(int k=0;k<yn;k++){
cin>>y;
t.push_back(y);
}
v.push_back(t);
table.push_back(v);
}
cout<<"***** TRANSITION TABLE OF NFA *****"<<endl;
print(table);
cout<<endl<<"***** TRANSITION TABLE OF DFA *****"<<endl;
vector<vector<vector<int> > > dfa;
vector<vector<int> > states;
states.push_back(closure(0,table));
queue<vector<int> > q;
q.push(states[0]);
while(!q.empty()){
vector<int> f=q.front();
q.pop();
vector<vector<int> > v;
for(int i=0;i<alpha;i++){
vector<int> t;
set<int> s;
for(int j=0;j<f.size();j++){
for(int k=0;k<table[f[j]][i].size();k++){
vector<int> cl= closure(table[f[j]][i][k],table);
for(int h=0;h<cl.size();h++){
if(s.find(cl[h])==s.end())
s.insert(cl[h]);
}
}
}
for(set<int >::iterator u=s.begin(); u!=s.end();u++)
t.push_back(*u);
v.push_back(t);
if(find(states.begin(),states.end(),t)==states.end())
{
states.push_back(t);
q.push(t);
}
}
dfa.push_back(v);
}
printdfa(states,dfa);
} Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}