"genereeritavasse" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

Tabeli alumise astme laiuseks saab analüüsitava sõna pikkus. Tipulahtrisse peab tekkima stardisümbol. Vahepealsetesse lahtritesse kirjutatakse mitteterminaal parajasti siis, kui ... Algoritmi tulemusena tekib lahtrisse mitteterminaal A, kui grammatikas G on esitatav tuletus A xjxj+1w, sõna kuulub keelde ning tipulahtris on stardisümbol. Keerukuseks n pikkuse sõna korral O(n3). 17. Earley algoritm. Ülesanne: kas sõna x kuulub grammatikaga G genereeritavasse keelde L. Üritame ehitada sõna vasaktuletust. G produktsiooni A v võib olla kasutatud sõna w = x1x2...xn (xi on terminaal) vasaktuletamiseks vaid siis, kui leidub tuletus: S =>* x1..xiA Kui sõna v koosneb alamsõnadest ja (v = ), peab leiduma tuletus: S =>* x1..xiA => x1..xi =>*x1.xi-1xi..xj (1) Earley algoritm moodustab massiivi || Iij ||, mille elementideks on punktiga produktsioonid. A . kuulub Iij koosseisu parajasti siis, kui sõna w = x1..xn