Teoreetilibe informaatika kordamisküsimused
Töötakt relatsioon konfiguratsioonide hulgal (aw, q 1) (w, q2), parajasti siis, kui
q2 kuulub delta(a,q1) kui üleminekufunktsioonis on lubatud a lugemisel minna
olekust q1 olekusse q2.
Lõpliku automaadi poolt aktsepteeritav keel:
Ü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')
annaabi.ee 
