#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <stdlib.h>
#include <conio.h>

using namespace std;

class Transition {
private:
    int Node;
    char Value;
public:
    friend class NFA;
    Transition(int _Node, char _Value = '\0') : Node(_Node), Value(_Value) {}
};

class NFA {
private:
    int Nodes;
    vector < vector <Transition> > Graph;
    set <int> Final;
public:
    NFA(int _Nodes) : Nodes(_Nodes) {Graph.resize(_Nodes);}
    void Insert(int, Transition);
    bool Accept(int, char*);
    void SetFinal(set <int> q) {Final = q;}
};

void NFA :: Insert(int Node, Transition A) {
    Graph[Node].push_back(A);
}

bool NFA :: Accept(int Curr, char* word) {
    if (word[0] == '\0') {
        if (Final.find(Curr) != Final.end()) return 1;
        return 0;
    }
    vector <Transition> :: iterator it;
    bool OK = 0;
    for (it = Graph[Curr].begin(); it != Graph[Curr].end(); ++it) {
        if ((*it).Value == word[0]) OK = max(OK, Accept((*it).Node, word + 1));
    }
    if (OK == 1) return 1;
    return 0;
}

int main()
{
    cout << "~~~~~~~IFRIMENCO ALEXANDRU - DANIEL - LIMBAJE FORMALE SI AUTOMATE - TEMA 1~~~~~~~~\n\n\n\n\n\n";
    cout << "PENTRU A SCHIMBA DATELE DESPRE AUTOMAT ACCESATI FISERUL DATE.IN\n\n";
    cout << "ORDINE DATE.IN:\nLINIA 1: NR. STARI\nLINIILE 2&3 : NR. STARI FINALE SI INDICELE ACESOTRA\nLINIA 4: M - NR. TRANZITII\nURMATOARELE M LINII - TRANZITILE\n";
    getch();
    system("cls");
    ifstream fin("date.in");
    int x, y, m, n;
    set <int> a;
    char z;
    fin >> n;
    NFA A(n);
    fin >> m;
    for (int i = 0; i < m; ++i) {
        fin >> x;
        a.insert(x - 1);
    }
    A.SetFinal(a);
    fin >> m;
    for (int i = 0; i < m; ++i) {
        fin >> x >> y >> z;
        Transition q(y - 1, z);
        A.Insert(x - 1, q);
    }
    int Curr;
    char word[100];
    cout << "Introduceti cuvantul care urmeaza a fi verificat si starea initiala\n";
    cin.get(word, 99);
    cin >> Curr;
    if (A.Accept(Curr - 1, word)) cout << "\n\nCUVANT ACCEPTAT\n";
    else cout << "CUVANT REFUZAT\n";
    return 0;
}