#include <stdio.h>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

vector<char> toVector(char *arr, int size){
     vector<char> vect;
     for (int i = 0; i < size; ++i)
     {
          if(arr[i] != ' ' && arr[i] != '\n' && arr[i] != '\0'){
               vect.insert(vect.end(), arr[i]);
          }
     }
     return vect;
}
void printVector(vector<char> vect){
  for(int i = 0; i < vect.size(); i++)
    printf("%c", vect[i]);
  cout << endl;
}
bool existValue(map < char, vector <char> > m, vector<char> v){
  bool fl = false;
  for(map < char, vector <char> >::iterator it = m.begin(); it != m.end(); it++){
    if(it->second.size() == v.size()){
      sort(it->second.begin(), it->second.end());
      sort(v.begin(), v.end());
      if(it->second == v)
        fl = true;
    }
  }
  return fl;
}
char getKey(map < char, vector <char> > m, vector<char> v){
  char key = ' ';
  for(map < char, vector <char> >::iterator it = m.begin(); it != m.end(); it++){
    if(it->second == v)
      key = it->first;
  }
  return key;
}

struct Rule
{
     char name[6];
};
int main()
{
     int numStates, numFinals, numAlphabet, numRules;
     //input n,m,k,l;
     printf("Enter the number of states: ");
     scanf("%d",&numStates);
     printf("Enter the number of final states: ");
     scanf("%d",&numFinals);
     printf("Enter the number alphabet symbols: ");
     scanf("%d",&numAlphabet);
     printf("Enter the number of rules: ");
     scanf("%d",&numRules);
     printf("\n-----------------------------------\n");
     //declare
     char *tmp;
     char start;
     vector<char> alphabet;
     vector<char> finals;
     vector<char> states;
     Rule rules[numRules];
     //input states
     tmp = new char[2*numStates];
     printf("Enter states (%d states): ", numStates);
     cin.ignore(10000, '\n');
     cin.get(tmp, 2*numStates);
     states = toVector(tmp, 2*numStates);
     delete []tmp;
     //input final states
     tmp = new char[2*numFinals];
     printf("Enter final states (%d states): ", numFinals);
     cin.ignore(10000, '\n');
     cin.get(tmp, 2*numFinals);
     finals = toVector(tmp, 2*numFinals);
     delete []tmp;
     //input start symbol
     printf("Enter start symbol (1 symbol): ");
     cin.ignore(10000, '\n');
     start = getchar();
     //input alphabet
     tmp = new char[2*numAlphabet];
     printf("Alphabet (%d symbols) : ", numAlphabet);
     cin.ignore(10000, '\n');
     cin.get(tmp, 2*numAlphabet);
     alphabet = toVector(tmp, 2*numAlphabet);
     delete []tmp;
     //input rules
     printf("Rules (%d rules):\n", numRules);
     for(int i = 0; i < numRules; i++)
     {
          cin.ignore(10000, '\n');
          cin.get(rules[i].name, 6);
     }
     printf("\n-----------------------------------\n");


     map < char, vector <char> > table;//tmp table
     map < char, vector <char> > detTable;// determ table
     vector<char> detFinals;//det final states
     //start new symbol
     char newSymb = 'A';
     //vector for groups of states
     vector<char> tmpVect;
     table[newSymb].push_back(start);
     detTable = table;
     //create table (new states -> old tates)
     do{
       table = detTable;
       for(map < char, vector <char> >::iterator iter = table.begin(); iter != table.end(); iter++){
         for(int i = 0; i < alphabet.size(); i++){
           for(int j = 0; j < iter->second.size(); j++){
             for(int k = 0; k < numRules; k++){
               //search rules: iter->second[j]_?_alphabet[i]
               if(rules[k].name[0] == iter->second[j] && rules[k].name[4] == alphabet[i]){
                 //add ? to vector
                 tmpVect.push_back(rules[k].name[2]);
               }
             }
           }
           //delete duplicated states from tmpVect
           sort(tmpVect.begin(), tmpVect.end());
           tmpVect.erase(unique(tmpVect.begin(), tmpVect.end()), tmpVect.end());
           //add new state to detTable if it doesn't exist
           if(!existValue(detTable, tmpVect) && tmpVect.size() != 0){
             newSymb ++;
             for(int k = 0; k < tmpVect.size(); k++){
               detTable[newSymb].push_back(tmpVect[k]);
             }
           }
           //clear vector
           tmpVect.clear();
         }
       }
     } while(detTable.size() != table.size());
     //print det table (new state -> old states)
     for(map < char, vector <char> >::iterator iter = detTable.begin(); iter != detTable.end(); iter++){
       cout << iter->first << " -> ";
       printVector(iter->second);
     }
     //print new rules
     cout << "New rules: " << endl;
     for(map < char, vector <char> >::iterator iter = detTable.begin(); iter != detTable.end(); iter++){
       for(int i = 0; i < alphabet.size(); i++){
         for(int j = 0; j < iter->second.size(); j++){
           for(int k = 0; k < numRules; k++){
             if(rules[k].name[0] == iter->second[j] && rules[k].name[4] == alphabet[i]){
               tmpVect.push_back(rules[k].name[2]);
             }
           }
         }
         sort(tmpVect.begin(), tmpVect.end());
         tmpVect.erase(unique(tmpVect.begin(), tmpVect.end()), tmpVect.end());
         cout << "(" << iter->first  << ", " << alphabet[i]<< ") -> " << getKey(detTable, tmpVect) << endl;
         tmpVect.clear();
       }
     }
     //print det finals
     for(map < char, vector <char> >::iterator iter = detTable.begin(); iter != detTable.end(); iter++){
       for(int i = 0; i < iter->second.size(); i++){
         for(int j = 0; j < finals.size(); j++){
           if(iter->second[i] == finals[j])
             detFinals.push_back(iter->first);
         }
       }
     }
     sort(detFinals.begin(), detFinals.end());
     detFinals.erase(unique(detFinals.begin(), detFinals.end()), detFinals.end());
     cout << "New final states: ";
     printVector(detFinals);
     return 0;
}