Convert NFA to DFA

This C++ assignment is for Theory of Computing, an introduction to the formal models of computation. Basically, everything is already written, it just needs the “code” where there are comments (no need to do anything else).

In the nfa.txt file, you must put the highest state number first.
Then on the subsequent lines
state char state state …. -1

Please note, we are using linux to compile the program, for example “g++ fa.cpp -o test”

*had to a txt for the cpp file, otherwise the form will not accept it. 

#name of file is nfadfaEC.cpp

#include<iostream>

#include<fstream>

#include<vector>

#include<string>

using namespace std;

// transform NFA into DFA  (nfa.txt into dfa.txt)

// 0 a 0 1 -1 =><0> a <01>

// States allowed are 0 through 9

// Arrows allowed are a through e

ofstreamfout (“dfa.txt”, ios::out);

vector<int> NFA[10][5];

intmaxState;  // the highest state indicated in nfa.txt first line

vector<string> DFA;

// —– utility functions —————————————-

// —————— end of utility ——————————

// Reads nfa.txt to build the NFA data structure

voidbuildnfa()

{

ifstream fin (“nfa.txt”, ios::in);

// **** code here *******************

fin.close();

}

// adds state to DFA if it is new

voidaddNewState(string state)

{

// *** code here ****************

}

// Main Driver

int main()

{

cout<< “Given your NFA in nfa.txt, this will produce the DFA in dfa.txt.” <<endl;

cout<< “State numbers must be 0 … 9” <<endl;

cout<< “Arrow labels can be anything from a .. e” <<endl<<endl;

buildnfa();

// add new states to DFA

addNewState(“0”);  // start with state 0

while (x <DFA.size() ) // for each DFA state

{

// display current DFA state S

// For each arrow

// go through each component state of S

// grab all destinations from NFA

// append the destinations to a state name DS

//If a transition on the arrow found, display it and send to dfa.txt

// and DS is added to DFA if new

}

fout<< “Any state with the original final state number is final” <<endl;

fout.close();

}

Solution

#include<iostream>

#include<fstream>

#include<vector>

#include<string>

using namespace std;

// transform NFA into DFA  (nfa.txt into dfa.txt)

// 0 a 0 1 -1 =><0> a <01>

// States allowed are 0 through 9

// Arrows allowed are a through e

ofstreamfout (“dfa.txt”, ios::out);

vector<int> NFA[10][5];

intmaxState;  // the highest state indicated in nfa.txt first line

vector<string> DFA;

// —– utility functions —————————————-

voiddisplayDFA()

{

cout<< “New States Are:” <<endl;

for (int i = 0; i <DFA.size(); i++)

{

cout<< “<” << DFA[i] << “> “;

}

cout<<endl<< “————-” <<endl;

}

// —————— end of utility ——————————

// Reads nfa.txt to build the NFA data structure

voidbuildnfa()

{

ifstream fin (“nfa.txt”, ios::in);

// **** code here *******************

cout<< “[Read in NFA]” <<endl;

if (fin >>maxState)

{

// read each line and add it into the NFA array

// assuming the input file is correct formatted.

int from, to;

char edge;

while (fin >> from >> edge)

{

cout<< “from ” << from << ” on ” << edge << ” goes to:”;

while (fin >> to && to != -1)

{

NFA[from][edge – ‘a’].push_back(to);

cout<< ” ” << to;

}

cout<<endl;

}

}

cout<<endl;

fin.close();

}

// adds state to DFA if it is new

voidaddNewState(string state)

{

// *** code here ****************

for (int i = 0; i <DFA.size(); i++)

{

if (DFA[i] == state) // already exist

{

return;

}

}

DFA.push_back(state);

}

// Main Driver

int main()

{

cout<< “Given your NFA in nfa.txt, this will produce the DFA in dfa.txt.” <<endl;

cout<< “State numbers must be 0 … 9” <<endl;

cout<< “Arrow labels can be anything from a .. e” <<endl<<endl;

buildnfa();

cout<< “[Build DFA]” <<endl;

// add new states to DFA

addNewState(“0”);  // start with state 0

int x = 0;

while (x <DFA.size() ) // for each DFA state

{

// display current DFA state S

displayDFA();

const string S = DFA[x];

cout<< “For the new state: <” << S << “>” <<endl;

cout<< ” Let’s check each row…” <<endl;

// For each arrow

for (char arrow = ‘a’; arrow <= ‘e’; arrow++)

{

// go through each component state of S

for (int i = 0; i <S.length(); i++)

{

int from = S[i] – ‘0’;

string DS;

const vector<int>&to = NFA[from][arrow – ‘a’];

// append the destinations to a state name DS

for (int j = 0; j <to.size(); j++)

{

DS += (char)(‘0’ + to[j]);

}

//If a transition on the arrow found, display it and send to dfa.txt

if (DS.length() > 0)

{

cout<< ”  Arrow ” << arrow << “: For component ” << from

<<” got ” << DS << ” from NFA.” <<endl;

cout<< ”      Thus from <” << S << “> on ” << arrow << ” goes to <”

<< DS << “>” <<endl;

fout<< “From <” << S << “> on ” << arrow << ” goes to <”

<< DS << “>” <<endl;

// and DS is added to DFA if new

addNewState(DS);

}

}

}

x ++;

}

fout<< “Any state with the original final state number is final” <<endl;

fout.close();

}