"produktsioonw" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

.Bk (,A), K>=0 Matemaatilise induktsiooniga saab näidata, et automaadi M korral kehtib (x,A)*(,) parajasti siis, kui kehtib A =>* x 20. KV-keelte tarvilikkuse tingimus. Süntaksipuu kõrgus ­ temas leiduva pikima tee kaarte arv. Tuletuspuu kõrgus vs sõna pikkus: Grammatikaga G genereeritava keele L sõna x pikkuse ning tema tuletuspuu kõrguse j vahel eksisteerib seos |x|produktsioonw) Tõestus: Näitame, et suvalise süntaksipuu T korral |Kr(T)|<= m j. Induktsioonibaas: j=1 ­ elementaarpuu .. intuitiivselt näha - triviaalne. Induktsioonisamm: Oletame, et väide kehtib, kuni kõrguseni k-1. Näitame, et sel korral kehtib sõna w süntaksipuu jaoks kõrgusel k. Sellise puu juurel max m vahetut alluvat, mille alluvate alampuude max kõrgus k- 1. Teiste puude kroonide pikkus on eelduse kohaselt m k-1. Kogu puu jaoks aga |Kr(T)| <= m * mk-1 = mk