#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <cstdlib>
#include <list>
#include <vector>
#include "Garnier-Gautier-Le-Gros-Viguier-automate.h"

using namespace std;

Transition TransitionCreee(Transition transition, string symbolee, string numero, string name, int nb_transi, string type)
{
    string ext (".txt");
    string base ("automates/A");
    string file = base + numero + ext;
    ifstream fichier(file.c_str(), ios::in);
    string tmp2;
    string tmp4;
    char tmp3;
    char tmp;
    int j = 0;

    transition.arrivee = new string [(nb_transi)*sizeof(string)]; /// On affecte un tableau qui stockera les etats d'arrivee, il aura, au plus, à stocker autant de valeurs qu'il y a de transitions

    for (int k = 0; k < nb_transi; k = k + 1) /// On affecte tous les transitions
    {
        transition.arrivee[k] = "-"; ///  à aucun etat d'arrivee
    }

    transition.symbole = symbolee; /// On affecte le symbole de cette transition

    if (type == "p") /// Si on est sur un etat poubelle
    {
        transition.arrivee[0] = "P"; /// Il boucle sur lui-même
    }
    else /// Sinon
    {
        if (fichier) /// Si on arrive à ouvrir le fichier contenant l'automate
        {
            for (int i = 0 ; i < 5 ; i = i + 1) ///On parcourt le fichier jusqu'à arriver aux transitions
            {
                getline(fichier, tmp2);
            }

            fichier.get(tmp);
            tmp2 = tmp;

            fichier.get(tmp3);
            tmp4 = tmp3;

            while(tmp2 != "!") /// Tant qu'on a des transitions
            {
                if (tmp2 == name && tmp4 == transition.symbole) ///Si on est sur le bon etat et sur le bon symbole
                {
                    fichier.get(tmp);
                    tmp2 = tmp;
                    transition.arrivee[j]=tmp2; /// Alors on initialise la première case libre du tableau d'arrivee avec l'etat d'arrivee de la transition
                    fichier.get(tmp);
                    fichier.get(tmp);
                    tmp2 = tmp;
                    j = j + 1;
                }

                else /// Sinon
                {
                    getline(fichier, tmp2); /// On passe à la ligne suivante
                    fichier.get(tmp);
                    tmp2 = tmp;
                }

                fichier.get(tmp3);
                tmp4 = tmp3;
            }
        }

        else /// Si le fichier ne s'ouvre pas
        {
            cerr << name << " Erreur !" << endl;
        }

        fichier.close();
    }

    return transition; ///On retourne la transition ainsi créée
}

Etat EtatCree(Etat etat, string name, string typee, int nb_symb, string numero, int nb_transi)
{
    etat.nom = name; /// On affecte le nom a l'etat
    etat.type = typee; /// On affecte son type a l'etat (Initial, Terminal, les deux, normal)
    Transition tmp;
    tmp.symbole="";
    string tmp2;

    if (typee == "p") /// Si on est sur un etat poubelle
    {
        cout << "Completion de l'etat " << etat.nom << endl << endl;
        for (int i = 0; i < nb_symb; i = i + 1)
        {
            char tmp3 = i + 97;
            string tmp4;
            tmp4 = tmp3;
            etat.transitions.push_back(TransitionCreee(tmp, tmp4, numero, name, nb_transi, "p")); /// On cree une transition poubelle
        }
    }

    else /// Sinon
    {
        for (int i = 0; i < nb_symb; i = i + 1) /// Pour chaque symbole reconnu par l'automate
        {
            char tmp3 = i + 97;
            string tmp4;
            tmp4 = tmp3;
            etat.transitions.push_back(TransitionCreee(tmp, tmp4, numero, name, nb_transi)); /// On cree toutes les transitions qui parte de l'etat et passent par ce symbole
        }

        cout << "Nom : " << etat.nom << endl; /// On affiche le nom de l'etat
        cout << "Type : "; /// On affiche son type

        if (etat.type == "i")
        {
            cout << "Initial" << endl;
        }

        else if (etat.type == "t")
        {
            cout << "Terminal" << endl;
        }

        else if (etat.type == "it")
        {
            cout << "Initial et terminal" << endl;
        }

        else if (etat.type == "p")
        {
            cout << "Poubelle" << endl;
        }

        else
        {
            cout << "Normal" << endl;
        }
    }

    return etat; /// On retourne l'etat nouvellment créé
}

Automate::Automate()
{
    nb_automate = 0; ///On crée un automate qui ne contient rien
    nb_symb = 0;
    nb_etats = 0;
    nb_etats_init = 0;
    nb_etats_term = 0;
    nb_transi = 0;
    etats_init = NULL;
    etats_term = NULL;
    etats.clear();
}

Automate::Automate(int num_automate)
{
    string tmp;
    nb_automate = num_automate;
    string base ("automates/A");
    string num;
    string ext (".txt");
    ostringstream convert;
    convert << num_automate;
    num = convert.str();
    string file = base + num + ext;
    bool init;
    bool term;
    string name;
    string cmp;
    Etat etat;

    ifstream fichier(file.c_str(), ios::in); /// On ouvre le fichier demandé par l'utilisateur

    if (fichier != NULL) /// Si on y arrive
    {
        fichier >> nb_symb >> nb_etats; /// On initialise les differents attributs de l'automate

        getline(fichier, tmp, ' ');
        istringstream (tmp) >> nb_etats_init;
        if (nb_etats_init != 0)
        {
            etats_init = new string[nb_etats_init*sizeof(string)];

            for(int i = 0; i < nb_etats_init; i = i + 1)
            {
                getline(fichier, tmp, ' ');
                etats_init[i] = tmp;;
            }
        }

        getline(fichier, tmp, ' ');
        istringstream (tmp) >> nb_etats_term;

        if (nb_etats_term != 0)
        {
            etats_term = new string[nb_etats_term*sizeof(string)];

            for(int i = 0; i < nb_etats_term; i = i + 1)
            {
                getline(fichier, tmp, ' ');
                etats_term[i] = tmp;
            }
        }

        fichier >> nb_transi;

        for (int i = 0; i < nb_etats; i = i + 1) /// De 0 au nombre d'etat de l'automate
        {
            init = false;
            term = false;

            for (int j = 0 ; j < nb_etats_init ; j = j + 1)
            {
                ostringstream convert;
                convert << i;
                cmp = convert.str();

                if (cmp == etats_init[j])
                {
                    init = true;
                }
            }

            for (int j = 0 ; j < nb_etats_term ; j = j + 1)
            {
                ostringstream convert;
                convert << i;
                cmp = convert.str();

                if (cmp == etats_term[j])
                {
                    term = true;
                }
            }

            if ((term == true) && (init == true)) ///On cree un etat
            {
                ostringstream convert;
                convert << i;
                name = convert.str();

                etats.push_back(EtatCree(etat, name, "it", nb_symb, num, nb_transi));
            }

            else if (term == true) ///On cree un etat
            {
                ostringstream convert;
                convert << i;
                name = convert.str();

                etats.push_back(EtatCree(etat, name, "t", nb_symb, num, nb_transi));
            }

            else if (init == true) ///On cree un etat
            {
                ostringstream convert;
                convert << i;
                name = convert.str();

                etats.push_back(EtatCree(etat, name, "i", nb_symb, num, nb_transi));
            }

            else ///On cree un etat
            {
                ostringstream convert;
                convert << i;
                name = convert.str();

                etats.push_back(EtatCree(etat, name, "n", nb_symb, num, nb_transi));
            }
        }

        fichier.close();
    }

    else
    {
        cerr << "Erreur a l'ouverture du fichier " << file << " !" << endl;
        cerr << "L'automate n'est pas initialise" << endl;
        nb_automate = -1; /// Pour savoir que l'automate est mal initialisee et donc inexploitable
    }
}

ostream& operator<<(ostream& os, const Automate& aAutomate)
{
    string stock;
    Etat tmp;
    Transition tmp2;
    Transition tmp3;

    /// On s'apprête à afficher l'automate

    os << "Automate n : " << aAutomate.nb_automate << endl; /// On affiche le nom

    if (aAutomate.nb_symb > 1) /// On affiche le nombre de symbole
    {
        os << "Alphabet de " << aAutomate.nb_symb << " symboles" << endl;
    }

    else
    {
        os << "Alphabet de " << aAutomate.nb_symb << " symbole" << endl;
    }

    if (aAutomate.nb_etats > 1) /// On affiche le nombre d'etats
    {
        os << "Automate avec " << aAutomate.nb_etats << " etats" << endl;
    }

    else
    {
        os << "Automate avec " << aAutomate.nb_etats << " etat" << endl;
    }

    if (aAutomate.nb_etats_init > 1) /// On affiche le nombre d'etat initiaux et on les affiche
    {
        os << aAutomate.nb_etats_init << " etats initiaux qui sont ";

        for (int i = 0; i < aAutomate.nb_etats_init; i = i + 1)
        {
            os << aAutomate.etats_init[i] << " ";
        }

        os << endl;

    }

    else if (aAutomate.nb_etats_init == 0)
    {
        os << aAutomate.nb_etats_init << " etat initial" << endl;
    }

    else
    {
        os << aAutomate.nb_etats_init << " etat initial qui est " << aAutomate.etats_init[0] << endl;


    }

    if (aAutomate.nb_etats_term > 1) /// On affiche le nombre d'etat terminaux et on les affiche
    {
        os << aAutomate.nb_etats_term << " etats terminaux qui sont ";

        for (int i = 0; i < aAutomate.nb_etats_term; i = i + 1)
        {
            os << aAutomate.etats_term[i] << " ";
        }

        os << endl;
    }

    else if (aAutomate.nb_etats_term == 0)
    {
        os << aAutomate.nb_etats_term << " etat terminal" << endl;
    }

    else
    {
        os << aAutomate.nb_etats_term << " etat terminal qui est " << aAutomate.etats_term[0] << endl;
    }

    if (aAutomate.nb_transi > 1) /// On affiche le nombre de transition
    {
        os << "Cet automate a " << aAutomate.nb_transi << " transitions" << endl;
    }

    else
    {
        os << "Cet automate a " << aAutomate.nb_transi << " transition" << endl;
    }

    list<Etat>::const_iterator
        lit (aAutomate.etats.begin()),
        lend (aAutomate.etats.end());

    list<Transition>::const_iterator
        lite (lit->transitions.begin()),
        lende (lit->transitions.end());

    for (;lite!=lende;lite++) /// On affiche chaque symbole
    {
        cout << "     " << lite->symbole;
    }

    cout << endl;

    for(;lit!=lend;lit++) /// Pour tous les etats
    {
        if (lit -> nom != "-")
        {
            cout << lit->nom << "     "; /// On affiche son nom

            list<Transition>::const_iterator
                litee (lit->transitions.begin()),
                lendee (lit->transitions.end());

            for(;litee!=lendee;litee++) /// Pour chacune de ses transitions
            {
                int i = 0;
                stock = litee -> arrivee[i];
                if (stock == "-") ///On affiche l'etat d'arrivee
                {
                    cout << stock <<"     ";
                }

                else
                {
                    while (stock != "-" && stock != "") ///On affiche l'etat d'arrivee
                    {
                        cout << stock;
                        i = i + 1;
                        stock = litee -> arrivee[i];
                        if (stock != "-" && stock != "") /// Si on a d'autres etats arrivee après
                        {
                            cout <<","; /// On affiche une virgule
                        }

                        else /// Sinon
                        {
                            cout <<"    "; /// On prepare l'affichage des arrivee suivante
                        }
                    }
                }
            }

            cout << endl;
        }

    }
    return os;
}

bool isDeterministe(Automate aAutomate)
{

    bool determ = true;
    string stock;

    list<Etat>::const_iterator
        lit (aAutomate.etats.begin()),
        lend (aAutomate.etats.end());

    if (aAutomate.nb_etats_init != 1) /// Si l'automate a plus d'un etat initial
    {
        determ = false; /// Il n'est pas deterministe
    }

    for(;lit!=lend;lit++)
    {
        list<Transition>::const_iterator
            lite (lit->transitions.begin()),
            lende (lit->transitions.end());

        for(;lite!=lende;lite++) /// Si pour chacune des transitions
        {
            stock = lite -> arrivee[1];
            if(stock != "-") /// Si on a plus d'un etat d'arrivee
            {
                determ = false; /// L'automate n'est pas deterministe
            }
        }
    }

    if (determ == true) /// Si l'automate est deterministe
    {
        cout << "L'automate est deterministe" << endl;
        return true; /// On le retourne
    }

    else /// Si l'automate n'est pas deterministe
    {
        cout << "L'automate n'est pas deterministe" << endl;
        return false; /// On le retourn
    }
}

bool isComplet(Automate aAutomate)
{
    bool complet = true;

    string stock;

    list<Etat>::const_iterator
        lit (aAutomate.etats.begin()),
        lend (aAutomate.etats.end());

    for(;lit!=lend;lit++) /// Pour chacun des etats
    {
        list<Transition>::const_iterator
            lite (lit->transitions.begin()),
            lende (lit->transitions.end());

        for(;lite!=lende;lite++) /// Pour chacune des transitions
        {
            int i = 0;
            stock = lite -> arrivee[i];

            if(stock == "-") /// Si une des transitions n'a pas d'etats d'arrivee
            {
                complet = false; /// Alors l'automate n'est pas complet
            }
        }
    }

    if (complet == true) /// Si l'automate est complet
    {
        cout << "L'automate est complet" << endl << endl;
        return true; /// Alors on le retourne
    }

    else /// Si l'automate n'est pas complet
    {
        cout << "L'automate n'est pas complet" << endl << endl;
        return false; /// Alors on le retourne
    }
}

void Completer(Automate& aAutomate)
{
    string stock;
    string num;
    Etat etat;
    bool comp = true;

    list<Etat>::const_iterator
        lit (aAutomate.etats.begin()),
        lend (aAutomate.etats.end());

    for(;lit!=lend;lit++) /// Pour chaque etat
    {

        list<Transition>::const_iterator
            lite (lit->transitions.begin()),
            lende (lit->transitions.end());

        bool affichage = false;

        for(;lite!=lende;lite++) /// Pour chaque transition
        {
            int i = 0;
            stock = lite -> arrivee[i];
            if(stock == "-") /// Si la transition n'a pas d'etat d'arrivee
            {
                lite -> arrivee[i] = "P"; /// Elle pointe vers la poubelle

                comp = false;

                if (affichage == false)
                {
                    cout << "Completion de l'etat " << lit->nom << endl; /// On affiche le nom de l'etat que l'on complete
                    affichage = true;
                }
            }
        }
    }

    ostringstream convert;
    convert << aAutomate.nb_automate;
    num = convert.str();

    if (comp == true) /// Si l'automate est complet
    {
        aAutomate.nb_transi = aAutomate.nb_etats*aAutomate.nb_symb; /// On met à jour le nombre de transition
    }


    if (comp == false) /// Sinon
    {
        aAutomate.etats.push_back(EtatCree(etat, "P", "p", aAutomate.nb_symb, num, aAutomate.nb_transi)); /// On ajoute l'etat poubelle
        aAutomate.nb_transi = (aAutomate.nb_etats)*aAutomate.nb_symb; ///On met à jour le nombre de transition
    }

}

void Determiniser(Automate aAutomate, Automate& bAutomate)
{
    int dim;

    if (aAutomate.nb_etats >= aAutomate.nb_transi)
    {
        dim = aAutomate.nb_etats+1;
    }

    else
    {
        dim = aAutomate.nb_etats;
    }

    vector < vector<string> > t_arrivee(aAutomate.nb_symb, vector<string>(dim)); /// On definit un tableau 2 dimensions pour stocker le symbole et les etats vers lesquels il amène
    vector <string> a_determ;
    vector <string> determ;
    vector <string> stockage;
    string tmp;
    string tmp2 = "";
    string stock;
    char tmp3;
    char* tmp4;
    bool init = false;
    bool term = false;
    Etat etat;
    int* taille = new int[aAutomate.nb_symb*sizeof(int)];
    int transi = 0;

    int nombre_etat = 0;
    int nombre_etat_term = 0;
    vector <string> etat_term;

    for (int i = 0 ; i < aAutomate.nb_symb ; i = i + 1)
    {
        taille[i] = 0;
    }

    bAutomate.nb_automate = aAutomate.nb_automate; /// On affecte au nouvel automate son numero
    bAutomate.nb_symb = aAutomate.nb_symb;/// Son nombre de symbole
    bAutomate.nb_etats_init = 1; /// Son nombre d'etat initial
    bAutomate.etats_init = new string [sizeof(string)];

    for (int i = 0; i < aAutomate.nb_etats_init; i = i + 1) /// On concatene tous les etats initiaux de l'automate de depart
    {
        ostringstream convert;
        convert << aAutomate.etats_init[i];
        tmp2 = convert.str();
        tmp = tmp + tmp2;
    }

    bAutomate.etats_init[0] = tmp; /// Pour faire l'etat initial de l'automate deterministe

    for (int i = 0; i < aAutomate.nb_symb; i = i + 1) /// On affecte les symboles dans le tableau
    {
        tmp3 = i + 97;
        t_arrivee[i][0].push_back(tmp3);
    }

    list<Etat>::const_iterator
        lit (aAutomate.etats.begin()),
        lend (aAutomate.etats.end());

    for(;lit!=lend;lit++) /// Pour chaque etat
    {
        list<Transition>::const_iterator
            lite (lit->transitions.begin()),
            lende (lit->transitions.end());

        for(;lite!=lende;lite++) /// Pour chaque transition
        {
            init = false;

            for (int i = 0; i < aAutomate.nb_symb; i = i + 1) /// Pour chaque symbole
            {
                ostringstream convert;
                convert << aAutomate.etats_init[i]; /// On recupere les etats initiaux de l'automate de base
                tmp2 = convert.str();

                if (lit -> nom == tmp2) /// Si l'etat actuel correspond a un etat initial
                {
                    init = true; /// On l'indique
                }

                if (init == true) /// Si l'etat est initial
                {

                    for (int k = 0; k < aAutomate.nb_etats_term; k = k + 1) /// On compare aux etats terminaux de l'automate de base
                    {
                        ostringstream convert;
                        convert << aAutomate.etats_term[k];
                        tmp2 = convert.str();

                        if (lit -> nom == tmp2) /// Si l'etat est terminal
                        {
                            term = true; /// On l'indique
                        }
                    }

                    if(lite -> symbole == t_arrivee[i][0]) /// Si le symbole de la transition correspond au symbole de la transition du nouvel etat initial
                    {
                        for(int j = 0 ; j < aAutomate.nb_transi ; j = j + 1) /// Pour chacune des transitions
                        {
                            tmp2 = lite -> arrivee[j]; /// On recupere l'etat d'arrivee

                            if (tmp2 != "-") /// Si il y a bien un etat d'arrivee
                            {
                                tmp4 = (char*)tmp2.c_str();
                                tmp3 = tmp4[0];
                                t_arrivee[i][j+1].push_back(tmp3); /// On l'insere dans un tableau en face de son symbole
                                taille[i] = taille[i] + 1; /// On indique que l'on a inséré un élément dans le tableau
                            }
                        }
                    }
                }
            }
        }
    }

    if (term == true) /// Si l'etat est aussi terminal
    {
        bAutomate.etats.push_back(EtatDeterm(etat, bAutomate.etats_init[0], "it", t_arrivee, bAutomate.nb_symb, taille, transi)); /// On cree un nouvel etat initial et terminal
        nombre_etat = nombre_etat + 1; /// On incrémente le nombre d'etat
        nombre_etat_term = nombre_etat_term + 1; /// On incrémente le nombre d'etat terminaux
    }

    else /// Sinon
    {
        bAutomate.etats.push_back(EtatDeterm(etat, bAutomate.etats_init[0], "i", t_arrivee, bAutomate.nb_symb, taille, transi)); /// On cree un nouvel etat inital
        nombre_etat = nombre_etat + 1; /// On incrémente le nombre d'etat
    }

    list<Etat>::const_iterator
        lite (bAutomate.etats.begin());

    list<Transition>::const_iterator
        litee (lite->transitions.begin()),
        lendee (lite->transitions.end());

    determ.push_back(bAutomate.etats_init[0]); /// Un vector qui stocke le nom des etats deja determinise pour ne pas les retraiter

    string tmp5;
    string tmp6;
    string smb;
    int ite;

    bool existant = false;

    for (;litee != lendee ; litee++) /// On rentre les états à déterminiser dans un vector
    {
        a_determ.push_back(litee->arrivee[0]); ///Un vector de string qui stocke les états d'arrivee
    }

    while (!a_determ.empty()) /// Tant qu'on a des états à déterminiser
    {
        existant = false;
        term = false;

        tmp2 = a_determ.front(); /// On récupère le premier état

        for (int i = 0 ; i < determ.size() ; i = i + 1) /// Pour chaque etat deja determinise
        {
            if (tmp2 == determ [i]) /// On verifie qu'on ne le redertiminise pas
            {
                existant = true;
            }
        }

        int length = tmp2.size();

        if(existant == false)
        {
            for (int i = 0 ; i < aAutomate.nb_symb ; i = i + 1) /// On affecte la taille de chaque tableau à 0
            {
                taille[i] = 0;
            }

            for (int i = 0 ; i < aAutomate.nb_symb ; i = i + 1) /// On nettoie chaque tableau censé stocker les etats d'arrivee
            {
                for (int j = 1 ; j < dim ; j = j + 1)
                {
                    t_arrivee[i][j].clear();
                }
            }

            for (int i = 0 ; i < length ; i = i + 1) /// On va  morceler l'etat recupere pour pouvoir le comparer aux états de base
            {
                tmp4 = (char*)tmp2.c_str();
                tmp3 = tmp4[i];
                tmp5 = tmp3;

                stockage.push_back(tmp5); ///On stocke l'etat de base aka le sous-etat


                for (int j = 0 ; j < aAutomate.nb_etats_term ; j = j + 1) /// Si l'etat est terminale, on le precise
                {
                    if (tmp5 == aAutomate.etats_term[j])
                    {
                        term = true;
                    }
                }

                while(!stockage.empty()) /// Tant qu'on a pas traite tous les sous-etats de l'etat actuel
                {
                    tmp6 = stockage.front();

                    list<Etat>::const_iterator
                        lyt (aAutomate.etats.begin());

                    for (; lyt!=lend; lyt++) /// Pour chaque etat
                    {

                        if(lyt->nom == tmp6) /// Si on travaille sur le bon etat
                        {
                            list <Transition>::const_iterator
                                lat (lyt -> transitions.begin()),
                                land (lyt -> transitions.end());

                            for(;lat!=land;lat++) /// Pour chaque transition
                            {

                                for(int j = 0 ; j < aAutomate.nb_transi ; j = j + 1)
                                {
                                    bool deja = false;

                                    tmp5 = lat -> arrivee[j]; /// On récupère l'état d'arrivee

                                    smb = lat -> symbole; /// On recupere le symbole

                                    tmp4 = (char*)smb.c_str();
                                    tmp3 = tmp4[0];
                                    ite = tmp3;

                                    ite = ite % 97; /// On se place dans le tableau a l'indice du symbole

                                    if (tmp5 != "-" && tmp5 != "") /// Si l'etat d'arrive est bien affecte
                                    {
                                        tmp4 = (char*)tmp5.c_str();
                                        tmp3 = tmp4[0];

                                        t_arrivee[ite][j+1].push_back(tmp3); /// On injecte l'etat dans le tableau final
                                        taille[ite] = taille[ite] + 1; /// On incremente la taille
                                    }
                                }
                            }
                        }
                    }

                    stockage.erase(stockage.begin()); /// On supprime le sous-etat que l'on vient de traiter
                }
            }

            if (term == true) /// Si l'etat est terminal
            {
                bAutomate.etats.push_back(EtatDeterm(etat, tmp2, "t", t_arrivee, bAutomate.nb_symb, taille, transi)); /// On crée un nouvel etat terminal
                nombre_etat = nombre_etat + 1;
                nombre_etat_term = nombre_etat_term + 1;
            }

            else /// Sinon
            {
                bAutomate.etats.push_back(EtatDeterm(etat, tmp2, "n", t_arrivee, bAutomate.nb_symb, taille, transi)); /// On crée un nouvel etat
                nombre_etat = nombre_etat + 1;
            }

            determ.push_back(tmp2); /// On ajoute l'etat que l'on de vient traiter à la liste des etats traites

            list<Etat>::const_iterator
                lut (bAutomate.etats.begin()),
                lund (bAutomate.etats.end());

            for (;lut!= lund ; lut++) /// Pour chaque etat du nouvel automate
            {
                list<Transition>::const_iterator
                    lot (lut->transitions.begin()),
                    lond (lut->transitions.end());

                for (;lot != lond ; lot++) /// Pour chacune des transitions
                {
                    bool present = false;

                    for (int k = 0 ; k < a_determ.size() ; k = k + 1) ///Pour chaque element à determiniser
                    {
                        if (a_determ[k] == lot -> arrivee[0]) /// Si l'etat d'arrivee de la transition est dedans
                        {
                            present = true; /// On l'indique
                        }
                    }

                    for (int k = 0 ; k < determ.size() ; k = k + 1) ///Pour chaque element que l'on a determinisé
                    {
                        if (determ[k] == lot -> arrivee [0]) /// Si l'etat d'arrivee de la transition est dedans
                        {
                            present = true; /// On l'indique
                        }
                    }

                    if (lot -> arrivee[0] == "-") /// Si l'etat d'arrivee n'est pas affecte
                    {
                            present = true; /// Il n'y a pas d'interet à le traiter
                    }

                    if (present == false) /// Si il n'est pas present
                    {
                        a_determ.push_back(lot->arrivee[0]); /// On l'ajoute a la liste des etats a determiniser
                    }
                }
            }
        }
        a_determ.erase(a_determ.begin()); /// On supprime l'etat que l'on vient de traiter
    }

    bAutomate.nb_etats = nombre_etat; /// On affecte le nombre d'etats de l'automate
    bAutomate.nb_etats_term = nombre_etat_term; /// On affecte le nombre d'etats terminaux
    bAutomate.nb_transi = transi; /// On affecte le nombre de transitions

    bAutomate.etats_term = new string [bAutomate.nb_etats_term*sizeof(string)]; /// On alloue la mémoire pour stocker les etats terminaux

    list<Etat>::const_iterator
        let (bAutomate.etats.begin()),
        led (bAutomate.etats.end());

    int i = 0;

    for (;let!=led; let++) /// Pour chaque etat
    {
        if ((let->type == "t") || (let->type == "it")) /// Si il est terminal
        {
            bAutomate.etats_term[i] = let->nom; /// On l'ajoute à la liste
            i = i + 1;
        }
    }
}

Etat EtatDeterm(Etat etat, string name, string typee, vector < vector<string> > t_arrivee, int nb_symb, int* taille, int& transi)
{
    etat.nom = name; ///Le nouvel etat reçoit son nom
    etat.type = typee; /// et son type

    Transition tmp;

    for (int i = 0; i < nb_symb; i = i + 1) /// Pour chaque symbole
    {
        etat.transitions.push_back(TransitionDeter(tmp, t_arrivee, i, taille, transi)); /// On cree les transitions qui y sont associées
    }

    return etat;

}

Transition TransitionDeter(Transition transition, vector < vector<string> > t_arrivee, int i, int* taille, int& transi)
{
    transition.arrivee = new string [2*sizeof(string)]; /// Comme il est deterministe, il suffit de 2 elements dans les etats d'arrivee

    string tmp = "";
    string tmp2 = "";
    string tmp3 = "";

    transition.symbole = t_arrivee[i][0]; /// On affecte le symbole de la transition

    for (int k = 0 ; k < taille[i] ; k = k + 1) /// On prepare le nom de l'etat d'arrivee de la transition
    {
        tmp = t_arrivee[i][k+1];

        tmp2 = tmp2 + tmp;
    }

    if (tmp2 == "") /// Si il n'y a pas d'etat d'arrivee
    {
        tmp2 = "-"; /// On l'indique
    }

    else /// Sinon
    {
        transi = transi + 1; /// On ajoute une transition
    }

    transition.arrivee[0] = tmp2; /// On affecte l'etat d'arrivee de la transition
    transition.arrivee[1] = "-";

    return transition;
}

void RecoMot(Automate aAutomate)
{
    string mot;
    char* tmp;
    char tmp2;

    bool pursuit = true;

    while(pursuit == true)
    {
        cout << "Saisissez un mot (mot vide : -) : "; /// L'utilisateur saisit un mot, - etant le mot vide
        cin >> mot;

        list <Etat>::const_iterator /// Pour chacun des etats
            lit (aAutomate.etats.begin()),
            lend (aAutomate.etats.end());

        if (mot == "-") /// Si le mot est vide
        {
            if (lit->type == "it") /// Si l'etat est initial et terminal
            {
                cout << "Le mot vide est reconnu"; /// Il reconnait le mot vide
            }

            else /// Sinon
            {
                cout << "Le mot vide n'est pas reconnu"; ///Il ne reconnait pas le mot vide
            }
        }

        else /// Sinon
        {
            bool recon = true;

            tmp = (char*)mot.c_str(); /// On récupère le mot rentré par l'utilisateur

            for (int i = 0 ; i < mot.size() ; i = i + 1) /// Pour chacun des caractères du mot
            {
                list <Transition>::const_iterator /// Pour chaque transition de l'état
                    lut (lit->transitions.begin()),
                    lund (lit->transitions.end());

                tmp2 = tmp[i]; /// On récupère le i-ème caractère
                string tmp3;
                string tmp4;
                string tmp5;

                tmp5 = tmp2;

                bool presence = false;

                for(;lut!=lund;lut++)
                {
                    tmp4 = lut->symbole; /// On récupère le symbole de la transition

                    if (tmp4 == tmp5) /// Si il est égal au caractère
                    {
                        tmp3 = lut->arrivee[0]; /// On stocke l'etat d'arrivee de la transition

                        while (tmp3 != lit -> nom) /// Tant qu'on est pas à cet etat
                        {
                            lit++; /// On itère l'état
                        }

                        presence = true; /// Et on valide la présence de la transition possible
                    }
                }

                if (presence == false) /// Si la transition n'est pas possible
                {
                    recon = false; /// Le mot n'est pas reconnu
                }
            }

            if (recon == true) /// Si le mot est reconnu
            {
                string tmp6;

                tmp6 = lit->type;

                if(tmp6 == "t" || tmp6 == "it") /// Si l'etat d'arrivee est terminal
                {
                    cout << "Le mot est reconnu " << endl; /// Le mot est reconnu
                }

                else
                {
                    cout << "Le mot n'est pas reconnu " << endl; /// Sinon le mot n'est pas reconnu
                }
            }

            else /// Sinon
            {
                cout << "Le mot n'est pas reconnu " << endl;
            }
        }

        system("pause");

        system("cls");

        cout << "Voulez-vous poursuivre la verification de mots ? <o/n> : ";
        cin >> mot;

        if (mot == "n")
        {
            pursuit = false;
        }
    }
}