# How to convert NFA to DFA

Are you stuck on an assignment that requires you to convert NFA to DFA? Would you like a helping hand? Get in touch with our coding experts right away. They are skilled in this area and would be happy to help you with your task.

## 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

#include

#include

#include

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 NFA;

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

vector 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

{

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

}

// Main Driver

int main()

{

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

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

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

buildnfa();

// add new states to DFA

while (x

{

// 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” <

fout.close();

}

Solution

#include

#include

#include

#include

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 NFA;

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

vector DFA;

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

voiddisplayDFA()

{

cout<< “New States Are:” <

for (int i = 0; i

{

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

}

cout<

}

// —————— 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]” <

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<

}

}

cout<

fin.close();

}

// adds state to DFA if it is new

{

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

for (int i = 0; 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.” <

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

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

buildnfa();

cout<< “[Build DFA]” <

// add new states to DFA

int x = 0;

while (x

{

// display current DFA state S

displayDFA();

const string S = DFA[x];

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

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

// For each arrow

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

{

// go through each component state of S

for (int i = 0; i

{

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

string DS;

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

// append the destinations to a state name DS

for (int j = 0; 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.” <

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

<< DS << “>” <

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

<< DS << “>” <

// and DS is added to DFA if new

}

}

}

x ++;

}

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

fout.close();

}