[rodney]

#include <iostream>
#include <set>
#include <queue>
#include <map>
#include <string>
#include <sstream>
using namespace std;

typedef char znak;
typedef int stanje;
const stanje nedefinirano = -1;
typedef pair<stanje,znak> parSZ;
typedef pair<stanje,stanje> parSS;
typedef map<parSZ,stanje> FunkcijaPrijelaza;

class DKA {
set<znak> Sigma;
set<stanje> Q, F; stanje q0;
FunkcijaPrijelaza delta;
public:
bool unesi();
bool unesi(string &);
bool prihvaca(string &);
bool zavrsno(stanje);
bool istovjetna(stanje, stanje);
bool podudarna (stanje, stanje);
void izbaciNedohvatljivaStanja();
void izbaciIstovjetnaStanja();
void ispisi();
stanje Delta(stanje, znak);
};

void DKA::izbaciIstovjetnaStanja() {
vector<set<stanje> > vs; vector<stanje> ozn;
set<stanje> s, tmp; set<stanje>::iterator i,j;
for (i=Q.begin(); i!=Q.end(); ++i) {
// za svako stanje i
if (s.count(*i)==0) {
// ako i nije iz s
s.insert(*i); tmp.insert(*i);
for (j=Q.begin(); j!=Q.end(); ++j) {
// cout << "Radim na paru " << (*i) << "," << (*j) << endl;;
if (istovjetna(*i,*j)) {
s.insert(*j); tmp.insert(*j);
}
}
if (tmp.size()>1) vs.push_back(tmp);
tmp.clear();
}
}
cout << "Istovjetna stanja: " << endl;;
for (int k=0; k<vs.size(); ++k) {
for (i=vs[k].begin(); i!=vs[k].end(); ++i) cout << (*i) << " ";
cout << endl;
}
/* za svako stanje i
ako i nije iz s
i ubaci u s i tmp
za svako stanje j
ako su (i,j) istovjetna
j ubaci u s i tmp
ako je u tmp vise od jednog elementa stavi tmp u vektor
isprazni tmp
*/
}


void DKA::izbaciNedohvatljivaStanja() {
set<stanje> D, done; queue<stanje> todo;
stanje s; todo.push(q0); D.insert(q0);
while (!todo.empty()) {
s = todo.front(); todo.pop(); done.insert(s);
// cout << "Radim na " << s << endl;
map<parSZ,stanje>::iterator i;
for (i=delta.begin(); i!=delta.end(); ++i) {
if ((i->first).first == s)
if (done.count(i->second)==0) { // if not done
D.insert(i->second); todo.push(i->second);
}
}
}
set<stanje>::iterator i;
cout << "Dohvatljiva stanja: ";
for (i=D.begin(); i!=D.end(); ++i) cout << (*i) << " ";
cout << endl;
}

bool DKA::unesi() {
string s; stanje i, j; znak z;
cout << "Unesite niz znakova abecede kao jednu rijec: ";
cin >> s; for (i=0; i<s.size(); ++i) Sigma.insert(s[i]);
cout << "Unesite skup stanja (niz prirodnih brojeva; -1 za kraj): ";
cin >> i; while (i >= 0) {Q.insert(i); cin >> i;}
cout << "Unesite pocetno stanje (prirodan broj): ";
cin >> q0; Q.insert(q0);
cout << "Unesite skup zavrsnih stanja (niz prirodnih brojeva; -1 za kraj): ";
cin >> i; while (i >= 0) {F.insert(i); Q.insert(i); cin >> i;}
cout << "Unesite funkciju prijelaza (trojke stanje,znak,stanje; -1,x,-1 za kraj): " << endl;
parSZ p; p.first = 1;
while (p.first >= 0) {
cout << "Unesite trojku: "; cin >> p.first >> p.second >> j;
if (Q.count(p.first)==0 || Q.count(j)==0
|| Sigma.count(p.second)==0 ) continue;
delta[p] = j; }
return true;
}

stanje DKA:elta(stanje s, znak z) {
parSZ p(s,z);
if (delta.count(p)==0) return nedefinirano;
return delta[p];
}





bool DKA::unesi(string &st) {
istringstream is(st); string s; stanje i, j; znak z;
// cout << "Unesite niz znakova abecede kao jednu rijec: ";
is >> s; for (i=0; i<s.size(); ++i) Sigma.insert(s[i]);
// cout << "Unesite skup stanja (niz prirodnih brojeva; -1 za kraj): ";
is >> i; while (i >= 0) {Q.insert(i); is >> i;}
// cout << "Unesite pocetno stanje (prirodan broj): ";
is >> q0; Q.insert(q0);
// cout << "Unesite skup zavrsnih stanja (niz prirodnih brojeva; -1 za kraj): ";
is >> i; while (i >= 0) {F.insert(i); Q.insert(i); is >> i;}
// cout << "Unesite funkciju prijelaza (trojke stanje,znak,stanje; -1,x,-1 za kraj): " << endl;
parSZ p; p.first = 1;
while (p.first >= 0) {
// cout << "Unesite trojku: ";
is >> p.first >> p.second >> j;
if (Q.count(p.first)==0 || Q.count(j)==0
|| Sigma.count(p.second)==0 ) continue;
delta[p] = j; }
return true;
}

void DKA::ispisi() {
cout << "M = (" << endl;
cout << " Sigma = { ";
set<znak>::iterator i;
for (i=Sigma.begin(); i!=Sigma.end(); ++i) cout << (*i) << " ";
cout << "}" << endl;
cout << " Q = {";
set<stanje>::iterator j;
for (j=Q.begin(); j!=Q.end(); ++j) cout << (*j) << " ";
cout << "}" << endl;
cout << " q0 = " << q0 << endl;;
cout << " F = {";
for (j=F.begin(); j!=F.end(); ++j) cout << (*j) << " ";
cout << "}" << endl;
cout << " delta = {";
map<parSZ,stanje>::iterator k;
for (k=delta.begin(); k!=delta.end(); ++k) {
cout << "d(" << (k->first).first << ",";
cout << (k->first).second << ")=" << (k->second) << "; ";
}
cout << "}" << endl << ")" << endl;
}









bool DKA:rihvaca(string &s) {
for (int i=0; i<s.size(); ++i) if (Sigma.count(s[i])==0) return false;
stanje q = q0;
for (int i=0; i<s.size(); ++i)
if ( (q=Delta(q,s[i])) == nedefinirano) return false;
if (F.count(q) != 0) return true;
return false;
}

bool DKA::zavrsno(stanje s) {
return (F.count(s)!=0);
}

















bool DKA:odudarna (stanje p, stanje r) {
if ( (Q.count(p)==0) || (Q.count(r)==0) ) return false;
if ( zavrsno(p) && !zavrsno(r) ) return false;
if ( !zavrsno(p) && zavrsno(r) ) return false;
return true;
}

bool DKA::istovjetna(stanje p, stanje r) {
queue<parSS> red; set<parSS> skup; parSS pss(p,r), tmp, novi; stanje s;
red.push(pss); skup.insert(pss);
while (!red.empty()) {
tmp = red.front(); red.pop();
for (set<znak>::iterator i=Sigma.begin(); i!=Sigma.end(); ++i) {
novi = parSS(Delta(tmp.first,*i),Delta(tmp.second,*i));
if (!podudarna(tmp.first, tmp.second)) return false;
if ( (skup.count(novi)==0) && (novi.first!=novi.second) )
red.push(novi);
skup.insert(novi);
}
}
return true;
}

int main () {
DKA M;
string s;
/* s += "abc "; //Abeceda
s += "1 2 3 -1 "; //Stanja
s += "1 "; //Pocetno stanje
s += "2 -1 "; //Zavrsna stanja
s += "1 a 1 "; s += "1 b 2 "; //Funkcija prijelaza...
s += "2 b 2 ";
s += "3 b 1 ";
s += "-1 x -1 ";
*/
s += "ab "; //Abeceda
s += "0 1 2 3 4 5 6 7 -1 "; //Stanja
s += "0 "; //Pocetno stanje
s += "4 6 -1 "; //Zavrsna stanja
s += "0 a 0 "; s += "0 b 3 "; //Funkcija prijelaza...
s += "1 a 2 "; s += "1 b 5 ";
s += "2 a 2 "; s += "2 b 7 ";
s += "3 a 6 "; s += "3 b 7 ";
s += "4 a 1 "; s += "4 b 6 ";
s += "5 a 6 "; s += "5 b 5 ";
s += "6 a 6 "; s += "6 b 3 ";
s += "7 a 6 "; s += "7 b 3 ";
s += "-1 x -1 ";
M.unesi(s); M.ispisi(); cout << endl;
s = "bbb"; cout << s << " : " << M.prihvaca(s) << endl;
s = "aaaa"; cout << s << " : " << M.prihvaca(s) << endl;
s = "aabbbb"; cout << s << " : " << M.prihvaca(s) << endl;
s = "aabbab"; cout << s << " : " << M.prihvaca(s) << endl;
s = "afbb"; cout << s << " : " << M.prihvaca(s) << endl;
cout << "Istovjetna : " << M.istovjetna(1,2) << endl;
cout << "Istovjetna : " << M.istovjetna(1,1) << endl;
cout << "Istovjetna : " << M.istovjetna(2,2) << endl;
M.izbaciNedohvatljivaStanja();
M.izbaciIstovjetnaStanja();
return 0;
}

Nije unos iz fajla, al to kazes vec imas :P