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:
Lõplike automaatide uurimiseks pole tingimata vaja füüsilise automaadi olemasolu. Kõige enam kasutatakse nende uurimiseks mitmesuguseid matemaatilisi mudeleid, mida nimetatakse abstraktseteks automaatideks. Kuna abstraktseid automaate saab kirjeldada algoritmikeelte abil, siis tuleneb sellest abstraktsete automaatide ning algoritmikeelte ekvivalentsus, s. t neid keeli on võimalik asendada abstraktsete automaatidega ja vastupidi. Üheks levinumaks ja kõige üldisemaks abstraktseks automaadiks on nn Turingi masin. Selle esitas 1936. a inglise loogik A M Turing. Masina tähtsus põhineb Turing-Churchi teesil, mille kohaselt igasuguse algoritmi infotöötluse võib sooritada Turingi masinaga. See väide ei ole matemaatiliselt tõestatav, sest algoritmi infotöötluse mõiste pole matemaatiline, vaid intuitiivne. Katsed leida algoritmilisi protsesse kajastav formaalne eeskiri, mis oleks võimsam kui Turingi masin, on olnud edutud. Seepärast loetakse tänapäeval algoritmilisteks
annaabi.ee 
