kuidas saab w1? 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
X magasini kirjutatav string Skeneeritav sõna aktsepteeritakse, kui pärast sõna läbimist on magasin tühi. Magasinmäluga automaat on struktuur: M = (,,Q,p,q0,$,F), kus - sisendtähestik (lint) magasini tähestik Q olekute tähestik p ( U {} x x Q ) üleminekufunktsioon q0 Q lähteolek $ - magasini lähtesümbol F Q lõppolekute hulk MMA (PDA) konfiguratsioon on kolmik: (w,,q) * x * x Q w lindil olev string magasinis olev string q hetkeolek Töötaktiks on binaarne relatsioon konfiguratsioonide hulgal: (aw,Za,q) (w,a,q'), kui (,q') kuulub p(a,Z,q) OR (w,Za,q) (w,a,q'), kui (,q') kuulub p(,Z,q) MMA poolt aktsepteeritav keel on hulk: T(M) = {w | (w,$,q0)*(,,r) , kus r on üks lõppolekutest} Iga KV keele jaoks leidub MMA, nii et L = T(M): G = (,N,P,S) Tõestuseks konstrueerime automaadi M nii: M = (,,Q,p,q0,$,F) = U N U {$} Q = {q0,q1,q2} Üleminekufunktsioon: p(,$,q0) = {(S$,q1)}
annaabi.ee 
