w2 w3 w4 w5 w6 w1 w2 w3 w4 w5 w6 11 Pinuautomaadid. KV grammatikat realiseeriv pinuautomaat. Pinuautomaat on lõplik automaat koos magasinmäluga. Magasini saab laadida sümboleid, see on lõpmatu DEF: Lõplik pinuautomaat on struktuur M = (Q, Σ(sisendid), Γ(magasin), δ, Q0, F) δ :Q×Σε×Γε →P(Q×Γε) (hetkeolek x sisend x magasinist loetu = olek x magasini pandu Automaat aktsepteerib sõne, kui ta alustab lähteolekust ja tühja magasiniga ning jõuab aktsept. olekusse. a,b → c (sisend, magasinist loetu = magasini pandu) ε - sisendist v magasinist ei loeta v ei kirjutata sinna Teoreem: Iga KV keel on aktsepteeritav mingi magasinmäluga automaadi abil. nt {0n1n | n>0 } vt üleval. Lõpliku magasinmäluga automaadi poolt aktsepteeritav keel on kontekstivaba. KV keelte hulk ongi see
ressurss ning mille täitmiseks moodustatakse juhtkirje, mille alusel protsessor eraldab ajaintervalle. *Kui programm on käskude jada, siis protsess on käskude täitmise järgnevus. *Protsessi kirjeldab programm, mida interpreteerib protsessor. Protsessi mõiste *Opsüsteem täidab mitmesuguseid töid: -Pakktööd -Aega jagavad tööd *Protsess- täitmisel olev programm. *Programmi täidetakse järjest. *Protsess koosneb: -Koodisektsioonist -Käsuloendurist -Magasinist -Anmesektsioonist -Protsessori seisust (registrid) Protsessi olek *Täitmise käigus satub protsess järgmistesse olekutesse: -Uus- protsess luuakse -Töös- selle protsessi käske täidetakse -Ootel- Protsess ootab mingi sündmuse toimumist -Valmis- protsess ootab, et tema käske täitma hakataks -Lõpetatud- protsessis olev programm on täidetud (edukalt või edutult) Protsessi juhtplokk *Iga protsessiga on seotud protsessi juht polkk (PCB) · Protsessi juhtplokk koosneb:
lõpus punkt.
Algoritmi ajaline keerukus O(n3) nii et praktikas suhteliselt vähe kasutatav.
18. Magasinmäluga automaadid
Seadeldis, millel on magasin ja lint ning mis on mõeldud KV keelte
aktsepteertimiseks. Lindilt saab lugeda iga sübolit üks kord sõna vasakult
paremale. Stacki läheb viimase oleku tähis. Töö algul tühja magasini tähis.
Automaadi käitumist määravad käsud kujul:
annaabi.ee 
