"redutseerituks" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

· Konstrueerime hulga P', millesse lisame järgmiselt:  o kui produktsioonid B pole ahelproduktsioon, lisame P'-sse A kõigi selliste mitteterminaalide A jaoks, mille korral B kuulus N A Ehk siis .. lisame uue grammatika produktsioonideks need, mille korral mitte-ahelproduktsioon B ei saa ahelproduktsiooniks Redutseeritud grammatika definitsioon: KV grammatikat G = (,N,P,S) nimetatakse redutseerituks, kui see ei sisalda tsükleid, -reegleid ja kasutuid sümboleid. Iga KV keele jaoks leidub genereeriv redutseeritud grammatika. 15. KV-grammatikate normaalkujud. Chomsky normaalkuju: KV-grammatika G = (,N,P,S) öeldakse olevat Chomsky normaalkujul, kui see sisldab produktsioone järgnevatel kujudel: A BC (kõik on mitteterminaalid) A b (b on terminaal, a mitteterminaal) S (S on lähtesümbol, mis ei esine ühegi produktsiooni paremas pooles)