View Single Post
Staro 25.03.2012., 17:32   #1
nosorog123
Registered User
 
Datum registracije: Mar 2012
Lokacija: zagreb
Postovi: 3
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:



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

Zadnje izmijenjeno od: nosorog123. 25.03.2012. u 17:53.
nosorog123 je offline   Reply With Quote