Implementing a code to simulate a finite automaton nondeterministic in c++

Question

I'm doing an assignment for automata theory, which I have to determine whether a word is accepted or not by a transition function for a deterministic finite automaton

I have this input file:

6 8 0 2
2
5
0 0 a
0 1 a
1 1 b
1 2 c
1 3 c
3 4 d
4 4 d
4 5 d
3
aaabcccc
aabbbbcdc
acdddddd

The input starts with 4 integers, the first is the number of state for the automaton, next is the number of transitions of the automaton, the third number is the initial state, and then the number of final states. then come the final states (in the example the final states are 2 and 5).

Then come N lines (N is the number of transitions), each with 2 integers and a character, I, J and C, representing the states where the transition, ie, the transition goes from state i to state J with the character C. Following this line come with a single integer S, which will contain the number of strings to test, then S lines with the respective strings.

The output of this program should be:

Case #2:
aaabcccc Rejected
aabbbbcdc Rejected
acdddddd Accepted

It should say if the String is accepted or rejected. So far, I've only coded the work with the input.

I don't know how would be most convenient to represent the automaton. Should I simply use arrays? What logic would I apply to the arrays?. Is there any way to do it without knowing in advance the automaton alphabet? Do I need a data structure to represent automata?. I am a little stuck with this assignment, and would like some ideas, some pseudocode or ideas to do it. Is the code in another language? I do not want the solution, because I want to do my assignment but if I could use some help

Sclaff

Im no expert on the topic might ask a silly question here. how come you have two transitions where you start from the same state and you arrive to different states with the same event/char triggering the transition? that means the states themselfs have an internal state too? – Aalst

@sergico: this is why such a graph is called non-determinist, sometimes there are several transitions. Therefore you need some back-tracking. All such automatons can be represented with a (much bigger) determinist automaton, but it may not be worth computing it. – Arboreal

Answer 1

I think you can have a maptr for transitions where tr[(i, c)] = j if there is transition from i state to j state via c, an array for final states fs[m] where m is the number of final states and an integer for the initial state s0.

Bellow is a frame of a class with such properties:

class Automata
{
public:
    Automata(int start) : s0(start)
    {}

    void add_transition(int i, int j, char c) {
        //...
    }

    void add_final_state(int i) {
        //...
    }

    bool validate_string(const std::string& str) {
        //...
    }
private:
    std::map<std::pair<int, char>, int> tr; // transitions
    std::vector<int> fs; // final states
    int s0; // initial state
};

Achievement

Not bad, at the exception of the transitions array. There may be several ways to transition from one state to another. A better representation is to have a mapping (State, Event) -> State. A std::map< std::pair<int, char>, int > would naturally fit here. – Arboreal

What is the function validate string? – Sclaff

That is, I guess I have to keep trying the chain and if at the end of this processing the string is then in a final state is accepted, is that right? – Sclaff

@MihranHovsepyan Hovsepyan I have a doubt, the automaton is nondeterministic, in the example of the entry, with the symbol "a" you can go to state zero to state 1. How I can treat this determinism in my code? I mean, what state I go to process the string? – Sclaff

@Sclaff For each finite nondeterministic automaton you can create equivalent finite deterministic automaton. en.wikipedia.org/wiki/… – Achievement