|
"Definicija automata koji prihvaća prihvatljivim stanjem":
IZVORNA DEFINICIJA |
"Definicija automata koji prihvaća praznim stogom":
GENERIRANA DEFINICIJA |
OPIS POSTUPKA PRETVORBE | |
|
1. red: skup stanja automata 2. red: skup ulaznih znakova 3. red: skup znakova stoga 4. red: početno stanje 5. red: znak dna stoga 6. red: skup prihvatljivih stanja 7. do zadnjeg reda: funkcija prijelaza oblika |
q0,q1,qp 0,1 J,N,K q0 K qp q0,$,K->qp,K q0,0,K->q0,NK q0,1,K->q0,JK q0,0,N->q0,NN#q1,$ q0,0,J->q0,NJ q0,1,N->q0,JN q0,1,J->q0,JJ#q1,$ q1,0,N->q1,$ q1,1,J->q1,$ q1,$,K->qp,K |
q0,q1,qp,qq,qe 0,1 J,N,K,X X q0,$,K->qp,K q0,0,K->q0,NK q0,1,K->q0,JK q0,0,N->q0,NN#q1,$ q0,0,J->q0,NJ q0,1,N->q0,JN q0,1,J->q0,JJ#q1,$ q1,0,N->q1,$ q1,1,J->q1,$ q1,$,K->qp,K qq,$,X->q0,KX qp,$,J->qe,$ qp,$,N->qe,$ qp,$,K->qe,$ qp,$,X->qe,$ qe,$,J->qe,$ qe,$,N->qe,$ qe,$,K->qe,$ qe,$,X->qe,$ |
1. preuzeli postojeće i dodali smo dva nova stanja 2. skup ulaznih znakova NE mijenjamo 3. preuzeli postojeće i dodali novi znak stoga 4. promijenili smo početno stanje 5. promijenili smo znak dna stoga 6. brišemo prihvatljiva stanja jer prihvaća praznim stogom 7. prepisujemo postojeće funkcije prijelaza i za novododano stanje qq gradimo prijelaz za epsilon i za novododani znak stoga X u početno stanje q0 i postavljamo tako da je novododani znak X na dnu stoga, a zadani početni na vrhu. Također za sva prihvatljiva stanja radimo kombinacije sa svim znakovima stoga i te funkcije prijelaza vode u novododano stanje qe i praznimo stog, jer želimo dobiti efekt kako prihvatljiva stanja zadanog automata prazne stog novo-generiranog automata. I naposlijetku istu metodu kao i za prihvatljiva stanja radimo i za novododano stanje qe |