Teoreetilibe informaatika kordamisküsimused
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
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
annaabi.ee 
