Implementing finite-state machine: run-time error, why?

Question

I know there are implementations of FSA available, but I'd love to know where is my mistake for learning purposes. The run-time error is usually when reading from input file with >>.

The error is 'exception thrown: exercise.exe has triggered a breakpoint'.

I've asked my classmates, but they were also unable to pin down the mistake.

Input:

1st line: number of states
2nd line: # of start state
3rd line: number of accept states
next several lines: #s of accept states
next line: number of transition functions
next several lines: transition functions, in form from to value, where from and to are corresponding states, and value is a symbol
next line: number of strings that we need to check for acceptance
next several lines: the strings themselves

My code is:

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <string>
using namespace std;

ifstream I("input.txt");
ofstream O("output.txt");

struct arrow {
    int destination=-1;
    char c='x';
    arrow() {}
    arrow(char val, int to) {
        destination = to;
        c = val;
    }
};
struct node {
    int name=-1;
    bool accept=false;
    int ars=0;
    arrow* arrows=new arrow;
    node() {}
    node(bool isAccept, int whatName) {
        accept = isAccept;
        name = whatName;
    }
};
class fsa {
    int start;
    node* states=new node;
public:
    fsa(int n, int entrSt, int acceptSts) {
        this->start=entrSt;
        int* tempForAcceptStates = new int[acceptSts];
        for (int i = 0; i < acceptSts; i++) I >> tempForAcceptStates[i];
        for (int i = 0; i < n; i++) { 
            int wasNodeCreated = -1;
            for (int j = 0; j < acceptSts; j++) {
                if (tempForAcceptStates[j] == i) wasNodeCreated = i;
            }
            if (wasNodeCreated >= 0) states[i] = node(true, wasNodeCreated);
            else { states[i] = node(false, i); }
        }
        int transitions;
        I >> transitions;
        for (int i = 0; i < transitions; i++) {
            int from, to;
            char val;
            I >> from >> to >> val;
            int temp = states[from].ars;
            this->states[from].arrows[temp] = arrow(val, to);
            states[from].ars++;
        }
    }
     bool isRecognized() {
         string str;
         getline(I, str);
         bool wasSymbolFound=false;
         int currentNode = this->start;
         for (int i = 0; i < str.length(); i++) {
             int howManyArsCurrentNodeHas = states[currentNode].ars;
             for (int j = 0; j < howManyArsCurrentNodeHas; j++) {
                wasSymbolFound = false;
                 if (states[currentNode].arrows[j].c == str[i]) {
                     currentNode = states[currentNode].arrows[j].destination;
                     wasSymbolFound = true;
                }
                 if (wasSymbolFound==true) break;
             }
             if (wasSymbolFound == false) return false;
         }
         if (states[currentNode].accept==true) return true; else return false;
     }
};

void main() {
    int n, entrSt, acceptSts;
    I >> n >> entrSt >> acceptSts;
    fsa A(n, entrSt, acceptSts);
    int words;
    I >> words;
    for (int i = 0; i < words; i++) {
        if (A.isRecognized()) O << "YES\n"; else O << "NO\n";
    }
    }

Example input:

3
0
1
0
6
0 1 a
1 0 b
0 2 b
1 2 a
2 2 a
2 2 b
3
ab
aaa
abababab

Corresponding desired output:

YES
NO 
YES

@RomeoValentin The error is 'exception thrown: exercise.exe has triggered a breakpoint'. — fragileradius

Christophe Christophe · Accepted Answer · 2019-11-23T16:09:09

Keep in mind that your file might not be found, or some formatting errors in the file might lead to read errors.

Unfortunately, you do no error checking, putting you as risk of UB, such as for example having random values in variables you thought properly read from the file. For example, on my system, trying your code without an input.txt file causes memory allocation exceptions to happen because acceptSts is a huge random number.

Now looking more in detail at what is hapening, even with a correct consistent input file as your example, your code is doomed to fail.

In in the fsa constructor you initialize the states member with new node, so a pointer to a single node. Later you assign or read from an indexed value, e.g. states[i], states[from], states[temp]. But at no moment did you allocate an array of nodes. So for every non zero index, you get UB, which could lead to memory corruption, abrupt program abortion, any other weird behavior, or no symptom at all.

You can correct this for example, by initializing the states in the constructor, since the finite states are known:

    states = new node[n];

Unfortunately, you have the same problem with arrow:

 states[from].arrows[temp] = arrow(val, to);

Not only was arrows in a node initailized with a pointer to a single arrow, causing the same issues as previously explained. THis is more complex to address with raw allocation. So my advice, go away from allocating arrays with new and try to use vector if you're allowed to. vectors can dynamically grow and are less error prone.

Not related:

using a global I and O and using it in class methods creates a hidden coupling, that makes the program difficult to debug. A better approach would be to define these fstream objects as local objects (e.g. of main()), and pass them as istream and ostream reference to the functions that need them.
if you allocate some pointers in a constructor, you should also delete it in a destructor, or you might leak memory. if you allocated with new[], then delete[].

Implementing finite-state machine: run-time error, why?

2 Answers