PC Ekspert Forum

PC Ekspert Forum (https://forum.pcekspert.com/index.php)
-   Web dizajn, programiranje i ostalo (https://forum.pcekspert.com/forumdisplay.php?f=39)
-   -   Pomoc za C++: Minimizacija DKA Automata (https://forum.pcekspert.com/showthread.php?t=231131)

nosorog123 25.03.2012. 17:32

Pomoc za C++: Minimizacija DKA Automata
 
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:

Code:

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:

http://i.imgur.com/I5wIq.png

za ulaznu txt datoteku oblika:
Code:

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 25.03.2012. 20:36

Tesko ti tko more pomoc bez koda....
Al evo imam nesto, moglo bi pomoc:




#include
#include
#include
#include
#include
#include
using namespace std;

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

class DKA {
set Sigma;
set 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 > vs; vector ozn;
set s, tmp; set::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 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 D, done; queue 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::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::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 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::Delta(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 // 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::iterator i;
for (i=Sigma.begin(); i!=Sigma.end(); ++i) cout << (*i) << " ";
cout << "}" << endl;
cout << " Q = {";
set::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::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::prihvaca(string &s) {
for (int i=0; i stanje q = q0;
for (int i=0; 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::podudarna (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 red; set 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::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 25.03.2012. 23:24

moj kod:





#include
#include
#include
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 26.03.2012. 01:11

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 27.03.2012. 10:50

da...oprosti zbog tog :(

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


Sva vremena su GMT +2. Sada je 23:54.

Powered by vBulletin®
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
© 1999-2024 PC Ekspert - Sva prava pridržana ISSN 1334-2940
Ad Management by RedTyger