Deterministic Finite-State Automaton Emulator C++

Write a program that reads in a description of a deterministic finite state automaton (FSA) from a data file. It should then prompt for (and read) input strings, one per line. Using each string as input to the FSA, your program should trace the progress of the FSA, at the end of which, it should print out whether or not the FSA accepts said string.

To keep things specific (and manageable), the input alphabet will be a finite set of characters, and the state set Q is a finite set of strictly positive integers. Moreover, well assume that all states are mentioned in the state transition table, which means that we dont need to know the number of states.

Input files will adhere to the following format.

A string, whose characters are the elements of . This string will not contain any blanks.

Number of states.

Start state.

Number of accepting states.

The accepting states.

Remainder of the file: state transition table.

Lets solve this problem via a FSA class, having the following public member functions:

A one-parameter constructor, whose parameter is an ifstream reference to the data file. The statement

FSA fsa{ifs};

initializes the FSA fas from ifs, where ifs is a variable of type ifstream. For simplicitys sake, theres no other way to initialize an FSA object. Ive made the statement FSA fsa; illegal by deleteing the (zero-parameter constructor in FSA.h.

describe(), a void function taking no parameters. The statement fsa.describe(); prints a description of fsa.

trace(), a void function taking one string parameter. The statement fsa.trace(in_string); traces the operation of the FSA object fsa on the input string in_string, indicating whether or not fsa accepts in_string at the end of the trace.

Given files:

FSA.cc (stub version of program):

#include "FSA.h"

#include #include #include #include

using namespace std;

// document me! FSA::FSA(ifstream &ifs) { cout << "called stub version of FSA constructor "; // do stuff here, the last action being get_state_table(ifs); }

// document me void FSA::get_state_table(ifstream &ifs) { cout << "called stub version of get_state_table() "; }

// document me void FSA::describe() { cout << "called stub version of describe() "; }

// document me void FSA::trace(const string& in_string) { cout << "called stub version of trace() "; }

FSA.h:

#pragma once

#include #include #include

class FSA { public: FSA(std::ifstream &ifs); FSA() = delete; // disallow 0-param ctor void describe(); void trace(const std::string& in_string); private: std::string sigma; // alphabet int num_states; // number of states int start_state; std::vector accept_states; std::vector> state_table; void get_state_table(std::ifstream &ifs); };

Proj1.cc:

#include "FSA.h" #include

using namespace std;

int main(int argc, char** argv) { // command-line argument munging if (argc != 2) { cerr << "usage: " << argv[0] << " fsa_file " << "where fsa_file is the data describing the FSA "; return 1; }

// open the FSA data file ifstream fsa_data(argv[1]); if (!fsa_data) { cerr << argv[0] << ": couldn't open " << argv[1] << endl; return 2; }

// initialize the FSA and print its description FSA fsa(fsa_data); cout << "FSA description: "; fsa.describe(); cout << endl;

// prompt-read-eval loop cout << "Enter input strings, one line at a time: "; while (true) { cout << "? "; string in_string; getline(cin, in_string); if (!cin) break; fsa.trace(in_string); } }

data1:

ab

3

1

1 2

2 1

3 3

2 1

Data2:

ab

4

1

2 1 4

1 2

3 4

2 1

3 4