Teoreetilibe informaatika kordamisküsimused
String:
· Tühi string e
· kui x on string ja a on sümbol, siis ax on string
· ainult nende kahe tingimusega määratud ühendid kuuluvad
Stringide konkatenatsioon (ex = xe = x).
Keel L on alamhulgaks *.
Keelte konkatenatsioon L = L1 ühend L2, kus L on alamhulgaks 1 ühend 2
L = (xy | x kuulub L1 AND y kuulub L2)
Keelte iteratsioon:
L* = ühend ühest n-ni Lk
L0 = e
Ln = Ln-1L, (n>0)
Homomorfism:
1 ja 2 on tähestikud. Kujutust h: 1* 2* nimetatakse homomorfismiks, kui
h(e) = e
h(ax) = h(a)h(x) iga a AND x kuulub 1* korral.
8. Fraasistruktuuri grammatikad. Chomsky klassifikatsioon.
Grammatika:
Formaalne aparatuur keele ja tema fraasistruktuuri esitamiseks.
Keel on teatud tähestiku = {a0, .., an} stringide alamhulk.
L = {x | x kuulub *, P(x)} alamhulgaks kõigi stringide alamhulgale.
Predikaat on semantika aluseks.
Terminaalide tähestik = keeele tähestik.
Mitteterminaalide tähestik N = hulk fraase tähistavaid metasümboleid
annaabi.ee 
