(60 pts.) Write a C++ class dfa for deterministic finite automata. The states are numbered 0, 1, ..., and state 0 is always the start state. All states has two transitions for characters and 1. The following member functions must be supported: o typedef std::size_t State; o typedef std::unordered_set StateSet; o constructor dfa (std::size_t n = 1, const StateSet &F = StateSet()): returns a new dfa with n > 1 states and accepting state set F. All transitions go to state 0. o std::size_t size() const: returns the number of states of this dfa; o StateSet F() const: returns the accepting state set. o State delta(State s, char x) const: returns 8(s,x) o void add_transition (State source, char symbol, State dest): changes transition in state source on input symbol to state dest; o State eval(const string & w) const: returns the final state of this dfa after reading input string w starting in state 0; o bool accept(const string & W) const: returns true iff this dfa accepts input string w starting in state 0. Also overload the input and output operators to allow reading and writing dfas. Use the following format for reading/writing dfas: nk al ... ak s_1 o di s_1 1 d2 // number of states and number of accepting states 17 accepting states 1/ transitions for each state s_n 0 d_{2n+1} s_n 1 d_{2n+2} We use (M) to refer to the above description of a dfa M. Report the output of this main program with input files input1.txt, input2.txt, input3.txt, and input4.txt. (60 pts.) Write a C++ class dfa for deterministic finite automata. The states are numbered 0, 1, ..., and state 0 is always the start state. All states has two transitions for characters and 1. The following member functions must be supported: o typedef std::size_t State; o typedef std::unordered_set StateSet; o constructor dfa (std::size_t n = 1, const StateSet &F = StateSet()): returns a new dfa with n > 1 states and accepting state set F. All transitions go to state 0. o std::size_t size() const: returns the number of states of this dfa; o StateSet F() const: returns the accepting state set. o State delta(State s, char x) const: returns 8(s,x) o void add_transition (State source, char symbol, State dest): changes transition in state source on input symbol to state dest; o State eval(const string & w) const: returns the final state of this dfa after reading input string w starting in state 0; o bool accept(const string & W) const: returns true iff this dfa accepts input string w starting in state 0. Also overload the input and output operators to allow reading and writing dfas. Use the following format for reading/writing dfas: nk al ... ak s_1 o di s_1 1 d2 // number of states and number of accepting states 17 accepting states 1/ transitions for each state s_n 0 d_{2n+1} s_n 1 d_{2n+2} We use (M) to refer to the above description of a dfa M. Report the output of this main program with input files input1.txt, input2.txt, input3.txt, and input4.txt