tuletuspuu. KV-grammatika, mille korral leidub sõna, millel on mitu tuletuspuud, nimetatakse mitmeseks. Teatud mitmestele grammatikatele leidub ekvivalentseid üheseid grammatikaid. KV keelt, millel leidub ühene genereeriv grammatika, nimetatakse üheseks, millel ei leidu, mitmeseks. KV-grammatika G on ühene, kui ei leidu keelde kuuluvaid sõnu, mille erinevad vasak-, paremtulemused omaksid erinevaid tuletuspuid (mitmene grammatika on see, mille korral leidub mitu erinevat vasaktuletust). Vasak- ja paremtuletus. 14. KV-grammatikate redutseerimine. Keele mittetühjuse kontroll: IN: KV grammatika G = (,N,P,S) OUT: Jah/Ei METHOD: Koostame hulgad N0,N1,... nii, et: · N0 = tühi, i=1 · Ni = Ni-1 U {A | A kuulub produktsioonide hulka, ja (Ni-1 U *)} ehk siis need sõnad, mis saab eelmiste sõnadest produktsioonil ühe terminaali lisamisega · Jätkame, kuni lisandub sõnu.
hulga A karakteristliku funktsiooni leidmiseks peab etteantud sõne w jaoks arvutama f(w) ja panema selle M-i sisendiks. Siis M-i väljund on A karakteristlik funktsioon. Teoreem: KV grammatikate ühesuse probleem pole lahenduv. T: selle saab redutseerida Posti vastavuse probleemile. Oletame, et grammatika G on ühene. Keel L (G) on kahe ühese keele La (G) ja Lb (G) ühend. Kui L(G) pole ühene, siis sõnedel, mis kuuluvad La ja Lb ühisossa, on kaks erinevat tuletuspuud (vasaktuletust). Kas aga neil keeltel on ühisosa? See on Posti vastavuse probleem, mis pole lahenduv. 28 Algoritmide keerukuse hindamine. Algoritmi keerukuse sõltuvus arvutamismudelist. DEF: Algoritmi keerukus on funktsioon f : N → N, mis seab sisendandmete mahule n vastavusse algoritmi sammude arvu (ajaline keerukus) või kasutatava mälu mahu (mahuline keerukus). ajaline keerukus – taktide / konfiguratsioonide arv; mahuline keerukus – kasutatud lindipositsioonide arv.
annaabi.ee 
