NFA

#include <bits/stdc++.h>
using namespace std;

vector<string> automata[100];
vector<string> symbols[100];
string start, finish, nfaState;
int numOfStates;

void takeInput();
string canReachUsingSymbol(string from, string symbol);
bool isValidCommand(string command);
int getNfaPosition(string command);
bool check(string command);

int main()
{
    takeInput();
    string command;

    while(true)
    {
        cout << "Enter command: ";
        cin >> command;

        if(check(command))
        {
            cout << "Valid command!\n";
        }
        else
        {
            cout << "Invalid command!\n";
        }
    } // end of while

    return 0;
}

void takeInput()
{
    cout << "How many states: ";
    cin >> numOfStates;

    cout << "Input starting state: ";
    cin >> start;

    cout << "Input ending state: ";
    cin >> finish;

    cout << "Input NFA state"
    << " (we assume that 0, 1 to go from this state to itself): ";
    cin >> nfaState; // 0, 1 to go to itself

    string temp;

    for(int i = 0; i < numOfStates; i++)
    {
        cout << "Enter name of the #" << i+1 << " state: ";
        cin >> temp;
        automata[i].push_back(temp); // first element is the state itself

        cout << "Which state can be accessed from " << temp
        << " (NULL if not any): ";
        cin >> temp;

        if(temp == "NULL") continue;

        automata[i].push_back(temp);

        symbols[i].push_back("NULL");

        cout << "Which is the symbol to go from " << automata[i][0]
        << " to " << temp << ": ";
        cin >> temp;
        symbols[i].push_back(temp);
    } // end of for
}

string canReachUsingSymbol(string from, string symbol)
{
    int stateIndex = -1;
    string reachable = "NULL";

    for(int i = 0; i < numOfStates; i++)
    {
        if(automata[i][0] == from)
        {
            stateIndex = i;
            break;
        }
    } // end of for

    if(stateIndex == -1) return reachable;

    for(int j = 1; j < automata[stateIndex].size(); j++)
    {
        if(symbols[stateIndex][j] == symbol)
        {
            return automata[stateIndex][j];
        }
    } // end of for

    return reachable;
} //////////////////////////////////////

bool isValidCommand(string command)
{
    string currentState = nfaState;
    string temp;

    for(int i = 0; i < command.size(); i++)
    {
        temp = "";
        temp += command[i];

        currentState = canReachUsingSymbol(currentState, temp);
    } // end of for

    return (currentState == finish);
} /////////////////////////////////////

int getNfaPosition(string command)
{
    int ans = -2;
    string currentState = start;
    string temp;

    // if the starting state is the NFA state
    if(start == nfaState) return 0;

    for(int i = 0; i < command.size(); i++)
    {
        temp = "";
        temp += command[i];

        currentState = canReachUsingSymbol(currentState, temp);
        if(currentState == nfaState)
        {
            ans = i + 1;
            break;
        } // end of if
    } // end of for

    return ans;
}

bool check(string command)
{
    int pos;

    pos = getNfaPosition(command);
    if(pos == -2) return false;
    if(nfaState == finish) return true;

    //cout << "pos: " << pos << endl;

    for(int i = pos ; i < command.size(); i++)
    {
        //cout << string(command.begin() + i, command.end() ) << endl;

        if( isValidCommand( string(command.begin() + i, command.end()) ) )
        {
            return true;
        }
    }

    return false;
}