"tipulahtris" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

Chomsky normaalkujul oleva grammatika ning terminaalse stringi korral otsustab, kas sõna kuulub keelde või mitte. Ühendab kõikvõimalikud tuletuspuud tuletuspäramiidiks. 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)