"mitteterminaalidest" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

X METHOD: V0 = {S}, i = 1 Vi = {X | A X on produktsioon AND A Vi-1} U Vi-1 Leiame sellised stringid, milleni viib produktsioon, lisame need sümbolid tähestikku Jätkame, kuni lisandub sümboleid, kui ei lisandu, siis N' = Vi lõige N (jäävad need, mis on mõlemas olemas) ' = Vi lõige P' = {A | A on produktsioon, A kuulub mitteterminaalide hulka ja on string terminaalidest ja mitteterminaalidest} G' = (',N',P',S) Kasutute sümbolite elimineerimine: Sümbolit nimetatakse kasutuks, kui sellest ei saa tuletada mingit stringi väljundisse IN: KV grammatika G = (,N,P,S) OUT: Ekvivalentne KV grammatika G' = (',N',P',S), mille korral L(G) = L(G') ja hulk N' U ' ei sisalda kasutuid sümboleid METHOD:  · Kasutades keele tühjuse algoritmi, koostame hulga Ne (viimase hulga, millele lisandus sümboleid) ja grammatika G1 = (,N lõige Ne,P1,S), kus