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[10][5];
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
voidaddNewState(string state)
{
// *** 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
addNewState(“0”); // start with state 0
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[10][5];
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
voidaddNewState(string state)
{
// *** 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
addNewState(“0”); // start with state 0
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
addNewState(DS);
}
}
}
x ++;
}
fout<< “Any state with the original final state number is final” <
fout.close();
}