"i0n" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

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 vasaktuletuse võib ehitada ülalnimetatud (1) osatuletuse jätkamise teel. Sõna kuulub keelde, kui produktsioon S v kuulub maatriksi elementi I0n. Antud: -vaba kontekstivaba grammatika + string x = x1 .. xn keele tähestiku stringide hulgast. Tulemus: maatriks Iij, kus 0<=i<=j<=n, i