Teoreetilibe informaatika kordamisküsimused
V*, tähistatakse =>G) lausevorm.
Grammatika poolt genereeritav keel L(G) = {w | w kuulub * AND w on kaudselt
tuletatav S0}.
Grammatikate hierarhia:
0-tüüpi (L0) .. ei lisakitsendusi
1-tüüpi (L1) .. kontekstist sõltuv
iga produktsiooni vasak pool on lühem kui parem pool
välja arvatud S -> e
2-tüüpi (L2) .. kontekstivaba
iga produktsioon kujul A w
A kuulub N, w kuulub V*
3-tüüpi (L3) .. paremlineaarsed keeled
kõik produktsioonid kujul A bC või A b
A,C kuulub N, b kuulub
L3 on alamhulgaks L2 on alamhulgaks L1 jne.
9. Regulaarsed avaldised ja hulgad.
Regulaarne hulk tähestikus :
· tühihulk
· {e} tühjast sõnast koosnev hulk
· {a} kuulub - ühest terminaalist koosnev hulk
· hulk P ühend Q, P lõige Q, Q*, kus P ja Q on regulaarsed hulgad
Regulaarne avaldis regulaarset hulka tähistav lühendkirjapilt, mis on määratud
annaabi.ee 
