Rekursiooni ja keerukusteooria eksami konspekt
M=(Q(olekud), Σ(tähestik), δ(üleminekufunktsioon), Q0(lähteolekud), F(lõppolekud))
δ : Q × Σε → P(Q) ükskõik mis tähe puhul või ka ilma sisendita (ε) läheb ühte Q kõigi alamhulkade hulgast.
(üleminekufunktsiooni asemel on hoopis relatsioon)
Olgu . Siis hulga A alamhulkade hulk on järgmine:
Teoreem: Iga mittedeterministik automaat N=(Q, Σ, δ,
Q0, F), mis aktsepteerib keelt A, on teisendatav sama
keelt aktsepteerivaks deterministlikuks lõplikuks
automaadiks
M = (Q’, Σ, δ′, Q0′, F′).
Kui mittedeterministlikul on k olekut, siis talle vastaval
deterministlikul võib olla kuni 2k olekut.
T: eeldame, et N-is pole ε-üleminekuid.
4 Regulaarsete avaldiste ja lõplike automaatide samaväärsus.
Teoreem: Regulaarse avaldisega defineeritud
keel on aktsepteeritav (mittedeterministliku)
lõpliku automaadiga.
T: vastavalt avadlise struktuurile saame
rekursiivselt teha automaadi:
annaabi.ee 
