"tuletatavust" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

· regulaarsete avaldiste p ja q, mis tähistavad vastavalt regulaarseid hulki P ja Q korral on regulaaravaldised ka: o p+q o pq o p* (p+ = pp*) Regulaarsed avaldised on võrdsed, kui tähistavad üht ja sama hulka. Regulaarsed hulgad tühihulk, {e} ja {a} on paremlineaarsed keeled. Kui keeled L1, L2 on paremlineaarsed, on paremlineaarsed ka nende ühend, vahe ja täiend. Tõestuseks koostan vastavad grammatikad .. ehk siis näitan kaudset tuletatavust. Järeldus: Regulaarne hulk on genereeritav paremlineaarse grammatikaga 10. Lõplikud automaadid. Mittedeterministlike automaatide teisendamine deterministlikeks. Automaat on algoritm, mis lahendab sõna keeles aktsepteerimise või mitteaktsepteerimise ülesannet. Lõplik automaat on viisik: M = (,Q,delta,Q0,F) sisendtähestik Q olekusümbolite lõplik tähestik delta üleminekuf.-n (Q P(Q) .. lähtuvalt produktsioonidest) Q0 lähteolekud (alamhulgaks olekutele)