"mittedeterministlick" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

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 |delta(a,q)| = n olekus q sümboli a lugemisel võrdvõimalik minna n olekusse Konfiguratsioon ­ paar (w,q) kuulub * x Q (aktiivne sümbol / lindile jäänud sõna + olek)  lähtekonfiguratisioon ­ (w,q0) q0 kuulub algolekute hulka lõppkonfiguratsioon ­ (e,r) r kuulub lõppolekute hulka Töötakt ­ relatsioon konfiguratsioonide hulgal (aw, q 1) (w, q2), parajasti siis, kui