"mittedeterministlike" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

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) F lõppolekud (alamhulgaks olekutele) Mittedeterministlick |delta(a,q)| <> 1 Deterministlick |delta(a,q)| = 1