Teoreetilibe informaatika kordamisküsimused
Ehk siis kui iga puu kaar esitab produktsiooni.
Iga puu on üheselt esitatav oma elementaarpuude nimistuna E(t) (elementaarpuu
on puu, mis koosneb vaid juurest ja terminaalsetest tippudest).
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:
annaabi.ee 
