Teoreetilibe informaatika kordamisküsimused
Näidata, et see on tarvilik ja piisav ja tingimus sõna aktsepteerimiseks:
Tarvilik:
Kui string on tuletatav 0 sammuga, siis saame kostrueerida ühest tipust
koosneva puu A[A] mis on süntaksipuu, kuna vastav produktsioon on
elementaarpuuks.
Iga produktsioon on esitatav elementaarpuuna ja iga elementaarpuu on kokku
kleebvitav suuremaks puuks.
Piisav:
Olgu antud ühe tipuga süntaksipuu saame 0-sammulise tuletuse. Iga alampuu
esitab terviklikku sõnajupi sünteesi .. igale elementaarpuule on vastavusse
seatav produktsioon ja muud polegi vaja.
Sõna tuletuspuu:
Täielikku süntaksipuud (mittelaiendatavat süntaksipuud mille juureks on
lähtesümobl ja lehtedeks ainult terminaalid) ning mille krooniks on string x
nimetatakse sõna x tuletuspuuks.
Sõna kuulub keelde, kui eksisteerib tuletuspuu, mille krooniks see sõna on.
Tuletuspuu on reeglina ka lause semantika näitaja (mitme tuletuspuu korral
mitmes erinevas tähenduses). Progemiskeelte korral igal lausel vaid 1
annaabi.ee 
