Question

DFA

Python DFA simulator

A deterministic finite automaton (DFA) - also known as deterministic finite state machine - is a finite state machine that accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automaton for each input string.

Write a DFA simulator using the python programming language.

Read your DFA from a textfile. First line contains a list of the final states (as integers), separated by a space. Rest of file contains the transitions in form: startstate, blank, symbol read, blank, tostate

1.Prompt user for name of file.

2.From there, program prompts the user for strings to test for acceptance on DFA.

3.Show the trace of the transitions through the machine along with whether the string is accepted or rejected.

4.Continue reading strings until user enters "quit."

Example input file... (ab)*

0

0a1

ob2

1a2

1b0

2a2

2b2

Files to Upload

•Upload a total of five (5) files: python file; output file (text file); input file (textile containing the DFa); a diagram of the DFA.

Answer 1

Solution:-

#include<iostream>

#include<stdio.h>

#include<string>

#include<fstream>

#include<vector>

using namespace std;

// Defining structure to hold current, next state and input character

struct state{

int current;

char input;

int next;

};

// This will contain list of final states

std::vector<int> finalStates;

// This will contain list of all states

std::vector<struct state> list_states;

/*

This method will read data from input file as provided by the user.

It will parse the file and find all states of the DFA and final states.

*/

void readData(){

char filename[255];

cout << "Please provide filename" << endl;

scanf("%[^\n]", filename);

cout << filename << endl;

try{

ifstream inFile;

inFile.open(filename);

string line;

int count = 0;

// reading data from file line by line.

while(getline(inFile, line)){

// converting string to char pointers

char str=const_cast< char >(line.c_str());

// Splitting string into tokens based on seperator " "

char *token = strtok(str, " ");

int index = 0;

state stat;

// if count is 0 it means its reading the first time i.e. the final states

if(count == 0){

while (token != NULL)

{

finalStates.push_back(stoi(token));

token = strtok(NULL, " ");

}

count++;

}else{

// otherwise, it reads each state line by line and prepares the list of states

while (token != NULL)

{

if(index == 0){

stat.current = stoi(token);

}else if(index == 1){

stat.input = token[0];

}else{

stat.next = stoi(token);

}

token = strtok(NULL, " ");

index++;

}

list_states.push_back(stat);

}

}

//Closing the file

inFile.close();

} catch (const char* msg) {

cerr << msg << endl;

}

}

/*

This method will check the input string and checks if it is accepted by the DFA or not

*/

bool checkInputString(string userInput){

// Considering fist state as input state

int currentState = list_states[0].current;

for(int i=0; i < strlen(userInput.c_str()); i++){

// Check in all states if the currenct state and current input character matches with any state

for(int j=0; j < list_states.size(); j++){

// if it matches then move to the next state.

if(currentState == list_states[j].current && userInput[i] == list_states[j].input){

currentState = list_states[j].next;

break;

}

}

}

// Finally, checks if current state is also in any of the final states, if so then input string is accepted

// otherwise not

bool found = false;

for(int i=0; i < finalStates.size(); i++){

if(finalStates[i] == currentState){

found = true;

break;

}

}

return found;

}

int main(){

// calling readData method

readData();

string userInput = "quit";

ofstream outputfile;

outputfile.open ("output.txt");

// Taking user's input until he/she quits.

do{

cout << "Provide input string (quit to exit)"<< endl;

cin >> userInput;

if(userInput != "quit"){

bool found = checkInputString(userInput);

if(found){

cout << "Accepted" << endl;

outputfile << userInput << ": " << "Accepted" << endl;

}else{

cout << "Not Accepted" << endl;

outputfile << userInput << ": " << "Not Accepted" << endl;

}

}

}while(userInput != "quit");

outputfile.close();

}

Output file containing information about each input with result is shown below [output.txt]:

abaaabb: Accepted
ababa: Not Accepted
aaaaaabbbababaaab: Not Accepted
aba: Accepted

Thank you...!