Teoreetilibe informaatika kordamisküsimused
Märgendatud järjestatud elementaarpuu esitab produktsiooni.
Mitteterminaalist A on tuletatav lausevorm parajasti siis, kui grammatikas G
leidub tuletuspuu A[].
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.
annaabi.ee 
