Implement the function dfa_is_accepted, which takes as input a DFA and a string, and determines if the DFA accepts the string.

DFA.cpp #include  #include "DFA.hpp" bool dfa_is_accepted (const DFA &m, const std::string &w) { return true; } std::ostream & operator << (std::ostream &out, const DFA &m) { out << m.numStates << std::endl; for (int q = 0; q < m.numStates; ++q) { out << m.transFunc [0][q] << ' ' << m.transFunc [1][q] << std::endl; } out << m.initialState << std::endl; out << std::count (m.finalStates.begin (), m.finalStates.end (), true) << ' '; for (int i = 0; i < m.numStates; ++i) { if (m.finalStates [i]) out << i << ' '; } out << std::endl; 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 < m.numStates; ++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 < k; ++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::ostream &out, const DFA &m); 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