Pomoc za C++: Minimizacija DKA Automata

[nosorog123]

Pozdrav,

Treba mi pomoc oko minimizacije DKA automata...
Ulazni podaci se dobivaju kroz .txt datoteku oblika:

Prvi red su sva imena stanja odvojena zarezima, drugi red su ulazni znakovi, treci red su prihvatljiva stanja, cetvrti red je pocetno stanje, peti i svi ostali su funkcije u prijelaza u obliku: trenutno stanje, ulazni znak-> iduce stanje.

npr. izgled ulazne txt datoteke:

stanje1,stanje2,stanje3,stanje4,stanje5,q3,z
a,befg,cce,ddd
stanje2,stanje5,q3
stanje1
stanje1,a->stanje2
stanje1,befg->q3
stanje1,cce->stanje5
...

Dosada sam: spremio sva stanja u 3D char matricu ovako:



za ulaznu txt datoteku oblika:

p1,p3,p4,p5,p6
c,d
p5
p1
p1,c->p6
p1,d->p3
p3,c->p1
p3,d->p5
p4,c->p4
p4,d->p6
p5,c->p6
p5,d->p3
p6,c->p4
p6,d->p1

na nultom redu u stranici mi je stanje a ostali redovi na toj stranici su stanja u koja to stanje prelazi za ulazni znak na istom redu npr: stanje p5 prelazi u stanje p6 za prvi ulazni znak, a za drugi ulazni znak prelazi u stanje p3 (isto ko i stanje p1)...

u 2D matricama imam spremljeno: listu prihvatljivih stanja, listu dohvatljivih stanja, pocetno stanje, listu ulaznih znakova (svaka lista jedna 2D matrica)

rjesio sam problem nedohvatljivih stanja...muci me kako implementirati algoritam za rjesavanje istovjetnih stanja...

pomocni linkovi:
http://hr.wikipedia.org/wiki/Determi...4%8Dni_automat
http://hr.wikipedia.org/wiki/Minimiz...8Dnog_automata

PS: na slici fali jos jedna stranica za stanje p6

ako moze bilo kakva pomoc sto prije zahvaljujem

[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

[nosorog123]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main () {
FILE *ulaz;
ulaz = fopen("lab.txt", "r");
char c, st[101][101][21], simb[101][21], prihv[101][21], poc[21], ld[101][21]={0};
int i=1, j=0, z=0, pisi_na=1, k, ret, nst, nsimb, nprihv;
//BEGIN UPIS
fscanf(ulaz, "%c", &c);
while (c != '\n') {
if (c != ',') { st[i][0][j] = c; j++; }
else { st[i][0][j] = '\0'; i++; j=0; }
fscanf(ulaz, "%c", &c);
}
nst = i;
i=1; j=0;
fscanf(ulaz, "%c", &c);
while (c != '\n') {
if (c != ',') { simb[i][j] = c; j++; }
else { simb[i][j] = '\0'; i++; j=0; }
fscanf(ulaz, "%c", &c);
}
nsimb = i;
i=1; j=0;
fscanf(ulaz, "%c", &c);
while (c != '\n') {
if (c != ',') { prihv[i][j] = c; j++; }
else { prihv[i][j] = '\0'; i++; j=0; }
fscanf(ulaz, "%c", &c);
}
if (prihv[1][0] == '\0')
nprihv = 0;
else nprihv = i;
fscanf(ulaz, "%s", poc);
j=1;
for (i=1; i<=(nst*2); i++)
for (j=1; j<=nsimb; j++) {
fseek(ulaz, (ftell(ulaz)+strlen(st[1][0])+strlen(simb[1])+5), SEEK_SET);
fscanf(ulaz, "%s", st[i][j]);
}
/*for (i=1; i<=nst; i++) {
for (j=0; j<=nsimb; j++)
printf("%s ", st[i][j]);
printf("\n");
}
printf("%s\n",poc);*/
//END UPIS
//BEGIN ALGORITAM ZA NEDOHVATLJIVA
for (i=0; i<=101; i++)
ld[i][0]=0;
strcpy(ld[0],poc);
while (ld[z][0] != 0) {
for (i=1; i<=nst; i++) {
if (strcmp(ld[z], st[i][0])==0) {
for (j=1; j<=nsimb; j++) {
for (k=0; k<=pisi_na; k++) {
if (strcmp(ld[k], st[i][j])==0) {ret=0; break;}
else ret=1;
}
if (ret) {strcpy(ld[pisi_na],st[i][j]); pisi_na++;}
}
}
}
z++;
}
//END ALGORITAM ZA NEDOHVATLJIVA


system ("PAUSE");
return 0;
}

[rodney]

Ako te muce istovjetna stanja, konc se na ovo:
Ispitivanje istovjetnosti stanja se može svesti na ispitivanje dva uvjeta:
Uvjet podudarnosti: Stanja p i q moraju oba biti prihvatljiva () ili oba neprihvatljiva ().
Uvjet napredovanja: Za bilo koji ulazni znak vrijedi da su stanja i istovjetna.

znaci neki pseudo kod (otprilike) bi bio

istovjetna(stanje1, stanje2)

{
-provjeri jesu li stanje 1 i stanje 2 oba zavrsna ili oba nezavrsna stanja (ako nisu vrati 0)
-ako za svaki ulazni znak x vrijedi istovjetna ((x stanje1), (x stanje2)) != 0 vrati 1
inace vrati 0
}

di (x stanje1) oznacava stanje u kojem je automat nakon sto u stanju1 procita x....
To je ovak odokativno.. Neznam sto ti nije jasnoo..
I da, kod ti je cisti c, ne c++, ako me oci ne varaju...

[nosorog123]

da...oprosti zbog tog

muci me kako saznati jesu li dva stanja istovjetna...