Attached are the files DFA.hpp and DFA.cpp for a simple data structure to represent a deterministic finite automaton.

Your task is to implement the function dfa_is_accepted, which takes as input a DFA and a string, and determines if the DFA accepts the string.

The version of g++ on the cs linux machines is recent as of the Summer of '15, which is to say, it is old. Please make sure it compiles there with the --std=c++11 flag, to give us a common baseline for running your code.

Submit your revised version of DFA.cpp, and answer the question: how did you test your code?

DFA.cpp:

DFA.hpp:

CODE

DFA.cpp:

#include

#include "DFA.hpp"

bool dfa_is_accepted (const DFA &m, const std::string &w)

{

return true;

}

std::ostream & operator

out

for (int q = 0; q

out

}

out

out

for (int i = 0; i

if (m.finalStates [i])

out

}

out

return out;

}

std::istream & operator >> (std::istream &in, DFA &m) {

in >> m.numStates;

boost::multi_array::extent_gen extents;

m.transFunc.resize (extents [2][m.numStates]);

for (int q = 0; q

in >> m.transFunc [0][q];

in >> m.transFunc [1][q];

}

in >> m.initialState;

m.finalStates.resize (m.numStates, false);

int k;

in >> k;

for (int i = 0; i

int q;

in >> q;

m.finalStates [q] = true;

}

return in;

}

DFA.hpp:

#ifndef DFA_HPP

#define DFA_HPP

#include

#include

#include

/* numStates is the number of states in the DFA

*

* transFunc is the transition function.

* For simplicity, we number the states 0..numStates-1, and assume the alphabet is {0,1}.

* transFunc [1][5] would be the new state we enter if we encounter a 1 in state 5.

*

* initialState is the initial state.

*

* finalStates is the set of final states.

* finalStates [q] is true if q is a final state, false otherwise.

*/

struct DFA {

int numStates;

boost::multi_array transFunc;

int initialState;

std::vector finalStates;

};

/* Read or write a DFA in a specific format:

* an integer, representing the number of states in the DFA

* two integers for each state, the new states reached after reading a 0 or 1

* an integer representing the initial state

* the number of final states

* a list of the final states

*

* For example, we could represent a DFA for strings in which the number of 1 bits is a multiple of 4:

* 4

* 0 1

* 1 2

* 2 3

* 3 0

* 0

* 1 0

*/

std::ostream & operator

std::istream & operator >> (std::istream &in, DFA &m);

// Determines if machine m accepts string w.

bool dfa_is_accepted (const DFA &m, const std::string &w);

#endif

1 #include #include "DFA. hpp" Nm D NO UNA 4 5 6 bool dfa_is_accepted (const DFA &m, const std::string &w) { return true; } 7 8 9 10 11 12 13 UN 16 std::ostream& operator > (std::istream &in, DFA &m) { in >> m.numStates; boost::multi_array::extent_gen extents; m.transFunc.resize (extents [2][m.numStates]); for (int q = 0; q > m. transFunc [@][9]; in >> m.transFunc [1][9]; } in >> m.initialState; m.finalStates.resize (m.numStates, false); int k; in >> k; for (int i = 0; i > 4; m.finalstates [9] = true; } return in; } = 35 36 37 38 39 40 = 41 42 43 44 45 1 2 4 5 NmL 00 OY 6 8 * ON co G DFA.hpp >... #ifndef DFA_HPA #define DFA_HPP 3 #include #include #include 7 /* numStates is the number of states in the DFA 9 10 transFunc is the transition function. 11 * For simplicity, we number the states 0..numStates-1, and assume the alphabet is {0,1}. 12 * transFunc [1][5] would be the new state we enter if we encounter a 1 in state 5. 13 14 * initialstate is the initial state. 15 16 * finalstates is the set of final states. 17 finalstates [q] is true if q is a final state, false otherwise. 18 19 struct DFA { 20 int numStates; 21 boost: :multi_array transFunc; 22 int initialstate; 23 std::vector finalStates; 24 }; 25 26 /* Read or write a DFA in a specific format: an integer, representing the number of states in the DFA 28 * two integers for each state, the new states reached after reading a @or 1 29 an integer representing the initial state 30 * the number of final states 31 a list of the final states 32 33 For ex le, we could represent a DFA for strings in which the number of 1 bits is a multiple of 4: 34 * 4 35 *@1 36 1 2 37 MONO 27 3 K si NO * 2 3 * 30 38 & * 10 39 40 41 42 43 std::ostream& operator