Teoreetilibe informaatika kordamisküsimused
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:
Rij = {w | (w, qi) * (e,qj)}
annaabi.ee 
