Ülalmainit' automaat aktsepteerib keele: T(M) = {w | (w,q0) * (e,r), q0 on algolek ja r on lõppolek } 11. Regulaarsete avaldiste, lineaarsete grammatikate ja lõplike automaatide samaväärsus. Iga lõpliku automaadi poolt aktsepteeritav keel on paremlineaarne Automaat M = (,Q,delta,Q0,F). Grammatika G = (,Q,P,S). Produktsioonide hulgaks saab: P = {q aq' | q' kuulub delta(a,q)} või {q a | delta(a,q) on lõppolek} või {S q0 | q0 on algolek} Produktsioonideks on üleminekud olekute vahel (konkateneerides loetud sümboli olemasolevasse stringi), kus üleminek on stardisübolist algolekusse, lõppolekusse või olekufunktsiooniga määratud olekusse. On ilmne, et: q =>*G wq' parajasti siis, kui (w,q) * (e,q') S =>* w parajasti siis, kui w kuulub T(M) Iga lõpliku automaadi poolt aktsepteeritav keel on regulaarne hulk L = T(M); M = (,Q,delta,Q0,F) Q = {q0, .., qn} Kõigi stringide hulk, mis viivad automaadi olekust qi olekusse qj:
annaabi.ee 
