Teoreetilibe informaatika kordamisküsimused
., 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
Stringid tähestikus V = ühend N on lausevormid.
Teisendusreegel e produktsioon kui lausevormide paar alfa -> beta.
Generatiivne grammatika e grammatika:
Nelik G = (,N,P,S0)
- terminaalide tähestik
N mitteterminaalide tähestik
P produktisoonide hulk
S0 stardisümbol
Lausevormis vahetult tuletatav (vahetu tuletatavus kui binaarne relatsioon hulgal
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
annaabi.ee 
