NFA -to- DFA

.cpp

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("citire.in");

class automatAFN
{
    string initiala;
    int nr_stari, nr_alf, nr_fin;
    vector<string> stari, alfabet, fin;
    vector< vector < vector< string > > > matrice;

public:
    friend class AFD;
    void parcurg();
    string concatenare(vector<string>&);
    automatAFN();
    ~automatAFN();
    void sorteaza();
    void sfarsit();
    void sortt(vector<string>&);
    void stari_finale();
    void adauga(int, int);
    void elimina(vector<vector< string> >);
    void elimin_repetitii();
    friend istream& operator>>(istream&, automatAFN&);
    friend ostream& operator<<(ostream&, automatAFN&);
};

class AFD
{
    int nr_stari, nr_fin,nr_alfabet;
    string q0;
    vector<string> stari, alfabet, fin;
    vector< vector< string > >afd;
    automatAFN afn;
    public:
        AFD();
        void finale();
        void creare(string);
        void adauga_starea(int st);
        friend ostream& operator<<(ostream&, AFD&);
        ~AFD();
};

void automatAFN:: elimina(vector<vector<string> > linie)
{

    for(int i=0;i<linie.size();i++)
    {
        for(int j=0;j<linie[i].size()-1;j++)
        for(int k=j+1;k<linie[i].size();k++)
        if(linie[i][k]==linie[i][j])
         {
            linie[i][k]=linie[i][linie[i].size()-1];
            linie[i].pop_back();
            k--;
    }}

     matrice.push_back(linie);
    for(int i=0;i<linie.size();i++)
    {for(int j=0;j<linie[i].size();j++) linie[i][j].clear();
    linie[i].clear();
    }
    linie.clear();

}

void automatAFN::sortt(vector<string>& vec)
{
    for(int i=0;i<vec.size();i++)
        for(int j=i+1;j<vec.size();j++)
        if(vec[i]>vec[j])
        swap(vec[i],vec[j]);
}

void automatAFN::sorteaza()
{
    for(int i=0;i<nr_stari;i++)
        for(int j=0;j<nr_alf;j++)
         sortt(matrice[i][j]);
}

int get_poz(vector<string>& sir, string& c)
{
    for(int i=0;i<sir.size();i++)
        if(sir[i]==c) return i;
    return -1;
}

void AFD::finale()
{
    for(int i=0;i<afn.nr_fin;i++)
        if(get_poz(stari,afn.fin[i])!=-1)
        {
            fin.push_back(afn.fin[i]);
            nr_fin++;
        }
}

ostream& operator<<(ostream& out, AFD& a)
{
    out<<"\nStarea initiala este ";
    out<<a.q0;
    out<<"\nStarile pentru afd sunt: ";
    for(int i=0;i<a.nr_stari;i++)
        out<<a.stari[i]<<" ";
    out<<"\nMatricea este : \n";
    for(int i=0;i<a.nr_stari;i++)
    {
        for(int j=0;j<a.nr_alfabet;j++)
            out<<a.afd[i][j]<<" ";
        out<<"\n";
    }
    out<<"\nStarile finale sunt ";
    for(int i=0;i<a.nr_fin;i++)
        out<<a.fin[i]<<" ";

    return out;
}

void AFD::adauga_starea(int st)
{
  if(st!=-1)
  {
  stari.push_back(afn.stari[st]);

  nr_stari++;
  vector<string> linie;
  for(int i=0;i<nr_alfabet;i++)
      linie.push_back(afn.matrice[st][i][0]);
    afd.push_back(linie);
  linie.clear();}
}

void AFD::creare(string sta)
{

    if(get_poz(stari,sta)==-1&&sta!="*")
    {
        adauga_starea(get_poz(afn.stari,sta));

        for(int i=0;i<nr_alfabet;i++)
        {
            string s;
            s=afd[get_poz(stari,sta)][i];
            if(get_poz(stari,s)==-1)
                    creare(s);
        }
    }

}
void automatAFN::stari_finale()
{
    vector<string> sf;
    for(int l=0;l<nr_fin;l++)
        for(int i=0;i<nr_stari;i++)
        for(int j=0;j<nr_alf;j++)
        for(int k=0;k<matrice[i][j].size();k++)
    if(fin[l]==matrice[i][j][k]) {string s; s=concatenare(matrice[i][j]); sf.push_back(s);}

    for(int i=0;i<sf.size()-1;i++)
        for(int j=i+1;j<sf.size();j++) { if(sf[i]==sf[j]) { sf.erase(sf.begin()+j); j--;}}

    fin.erase(fin.begin());
    for(int i=0;i<sf.size();i++) fin.push_back(sf[i]);
    nr_fin=fin.size();
    sf.erase(sf.begin());

}

void automatAFN::sfarsit()
{
    for(int i=0;i<nr_stari;i++)
        for(int j=0;j<nr_alf;j++)
        if(matrice[i][j].size()>1)
    {
        string s; s=concatenare(matrice[i][j]);
        matrice[i][j].resize(1);
        matrice[i][j][0]=s;
    }

}

ostream& operator<<(ostream& out, automatAFN& a)
{   out<<"\nStarile sunt: ";
    a.nr_stari=a.stari.size();
    for(int i=0;i<a.nr_stari;i++) out<<a.stari[i]<<" ";
    out<<"\nAlfabetul este: ";
    for(int i=0;i<a.nr_alf;i++) out<<a.alfabet[i]<<" ";

    out<<"\nMatricea este : \n";
     for(int i=0;i<a.stari.size();i++)
    {for(int j=0;j<a.alfabet.size();j++)
    {for(int k=0;k<a.matrice[i][j].size();k++)
    out<<a.matrice[i][j][k]<<" ";
    out<<"   ";}
    out<<endl;}
    out<<"\nStarile finale sunt: ";
    for(int i=0;i<a.nr_fin;i++)
        out<<a.fin[i]<<" ";

return out;
}

istream& operator>>(istream& in, automatAFN& a)
{
    f>>a.initiala;
    f>>a.nr_stari>>a.nr_alf>>a.nr_fin;
    a.stari.resize(a.nr_stari);
    for(int i=0;i<a.nr_stari;i++) f>>a.stari[i];
    a.alfabet.resize(a.nr_alf);
    for(int i=0;i<a.nr_alf;i++)   f>>a.alfabet[i];
    a.fin.resize(a.nr_fin);
    for(int i=0;i<a.nr_fin;i++)   f>>a.fin[i];

    a.matrice.resize(a.nr_stari);
    for(int i=0;i<a.nr_stari;i++)
        a.matrice[i].resize(a.nr_alf);

    string x,y,z;
    while(f>>x>>y>>z)
   {  a.matrice[get_poz(a.stari,x)][get_poz(a.alfabet,y)].push_back(z);}
    for(int i=0;i<a.nr_stari;i++)
        for(int j=0;j<a.nr_alf;j++)
        if(a.matrice[i][j].empty()) a.matrice[i][j].push_back("*");

    return in;
}


automatAFN::~automatAFN()
{

    for(int i=0;i<nr_stari;i++) stari[i].erase();
    stari.clear();
    for(int i=0;i<nr_alf;i++)   alfabet[i].erase();
    alfabet.clear();
    for(int i=0;i<nr_fin;i++)   fin[i].erase();
    fin.clear();

    for(int i=0;i<nr_stari;i++)
       {
        for(int j=0;j<nr_alf;j++)
        matrice[i][j].clear();
        matrice[i].clear();
       }
    matrice.clear();
    nr_stari=nr_alf=nr_fin=0;
}

automatAFN::automatAFN()
{
    nr_stari=nr_alf=nr_fin=0;
}

string automatAFN::concatenare(vector<string>& v)
{

    string rez;
    rez=v[0];
    if(v.size()>1)
        for(int i=1;i<v.size();i++)
        rez+=v[i];
    return rez;
}

void automatAFN::elimin_repetitii()
{
    for(int i=0;i<nr_stari;i++)
    for(int j=0;j<nr_alf;j++)
    {for(int k=0;k<matrice[i][j].size()-1;k++)
    for(int l=k+1;l<matrice[i][j].size();l++)
    if(matrice[i][j][k]==matrice[i][j][l])
         matrice[i][j].erase(matrice[i][j].begin()+l-1);
    }
}


void automatAFN::adauga(int x, int y)
{
    string s;
    sorteaza();
    s=concatenare(matrice[x][y]);

  //  cout<<"Adaug starea "<<s<<endl;
    stari.push_back(s);
    nr_stari=stari.size();
    vector <vector<string> >  linie;
 for(int j=0;j<nr_alf;j++)
    {   vector<string> elemente;
        for(int i=0;i<matrice[x][y].size();i++)
        for(int k=0;k<matrice[get_poz(stari,matrice[x][y][i])][j].size();k++)
        {if (matrice[get_poz(stari,matrice[x][y][i])][j][k]!="*")
          elemente.push_back(matrice[get_poz(stari,matrice[x][y][i])][j][k]);}
         if(elemente.empty()) elemente.push_back("*");
        linie.push_back(elemente);
        for(int i=0;i<elemente.size();i++) elemente[i].clear();
        elemente.clear();
    }
    elimina(linie);
    for(int i=0;i<linie.size();i++)
    {for(int j=0;j<linie[i].size();j++) linie[i][j].clear();
    linie[i].clear();
    }
    linie.clear();
}

void automatAFN::parcurg()
{
        for(int i=0;i<nr_stari;i++)
            for(int j=0;j<nr_alf;j++)
           {
               if(matrice[i][j][0]!="*")
                if(matrice[i][j].size()>1)
                {string c;
                c=concatenare(matrice[i][j]);
                if(matrice[i][j].size()>1)
                    if(get_poz(stari,c)==-1)
                        adauga(i,j);
                }
            //     elimin_repetitii();
           }
}
AFD::~AFD()
{
    for(int i=0;i<nr_stari;i++) stari[i].clear();
    stari.clear();
    for(int i=0;i<nr_alfabet;i++) alfabet[i].clear();
    alfabet.clear();
    for(int i=0;i<nr_fin;i++) fin.clear();
    fin.clear();
    for(int i=0;i<nr_stari;i++)
       {for(int j=0;j<nr_alfabet;j++)
        afd[i][j].clear();
        afd[i].clear();
       }
       afd.clear();

    nr_stari=nr_alfabet=nr_fin=0;
       }


AFD::AFD()
{
    cin>>afn;
    afn.parcurg();
    afn.sorteaza();
    afn.stari_finale();
    afn.sfarsit();
    //cout<<afn;
    nr_fin=nr_stari=0;
    q0=afn.initiala;

    nr_alfabet=afn.nr_alf;

    for(int i=0;i<nr_alfabet;i++) alfabet.push_back(afn.alfabet[i]);

    string stare;
    stare=q0;
    creare(stare);
    finale();
}

int main()
{
    AFD b;
    cout<<b;
    f.close();
    return 0;
}

.txt

// https://www.tutorialspoint.com/automata_theory/ndfa_to_dfa_conversion.htm 
// Fisierul de intrare: 
a
5 2 1
a
b
c
d
e
0
1
e
a 0 a
a 0 d
a 0 e
a 0 b
a 0 c
a 1 e
a 1 d
c 1 b
b 1 e
b 0 c
d 0 e