Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Write a C++ class dfa for deterministic finite automata. The states are numbered 0,1,...0,1,..., and state 0 is always the start state. All states has

Write a C++ class dfa for deterministic finite automata. The states are numbered 0,1,...0,1,..., and state 0 is always the start state. All states has two transitions for characters 0 and 1. The following member functions must be supported:

  • typedef std::size_t State;
  • typedef std::unordered_set StateSet;
  • constructor dfa(std::size_t n = 1, const StateSet &F = StateSet()): returns a new dfa with n1n1 states and accepting state set FF. All transitions go to state 0.
  • std::size_t size() const: returns the number of states of this dfa;
  • StateSet F() const: returns the accepting state set.
  • State delta(State s, char x) const: returns (s,x)(s,x)
  • void add_transition(State source, char symbol, State dest): changes transition in state source on input symbol to state dest;
  • State eval(const string & w) const: returns the final state of this dfa after reading input string w starting in state 0;
  • 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:

 n k // number of states and number of accepting states a1 ... ak // accepting states s_1 0 d1 // transitions for each state s_1 1 d2 ... 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.

Below is the complete code of main program, please write dfa.h:

main:

#include  #include  #include "dfa.h" #include  #include  #include  using namespace std; std::string bin(std::size_t n) { std::string ans; while (n > 0) { if (n % 2 == 1) ans = '1' + ans; else ans = '0' + ans; n /= 2; } return ans; } int main() { srand(time(0)); int N(1000); { ifstream is("input1.txt"); if (is.fail()) { cout > M; for (int i = 1; i > M; for (int i = 1; i > M; for (int i = 1; i > M; for (int i = 1; i  

input1.txt:

4 2 2 3 0 0 0 0 1 1 1 0 2 1 1 3 2 0 0 2 1 1 3 0 2 3 1 3

input2.txt:

3 1 0 0 0 0 0 1 1 1 0 2 1 1 0 2 0 1 2 1 2

input3.txt:

6 1 4 0 0 1 0 1 1 1 0 2 1 1 2 2 0 3 2 1 3 3 0 4 3 1 4 4 0 5 4 1 5 5 0 5 5 1 5

input4.txt:

1 0 0 0 0 0 1 0

image text in transcribed

5. (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 0 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 (,2) 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: al ... ak s 1 o di 5_1 1 d2 // number of states and number of accepting states // accepting states // transitions for each state s_nod_{2n+1} s_n 1 d_{2n+2} We use (M) to refer to the above description of a dfa M. 5. (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 0 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 (,2) 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: al ... ak s 1 o di 5_1 1 d2 // number of states and number of accepting states // accepting states // transitions for each state s_nod_{2n+1} s_n 1 d_{2n+2} We use (M) to refer to the above description of a dfa M

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Bioinformatics Databases And Systems

Authors: Stanley I. Letovsky

1st Edition

1475784058, 978-1475784053

More Books

Students also viewed these Databases questions