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 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.
DEF: näiteks kui α = γNδ ja β =γφδ ja grammatikas leidub produktsioon N → φ. kui α-st saab β mitme järjest tuletussammuga: tuletatav α + β kui α-st saab β k sammuga, kirjutatakse α k β; kui α = β või α + β , kirjutatakse α ∗ β DEF: α ∗ β, kui mingi k ∈ {0, 1, 2, . . .} korral α k β. 8 KV keeled. KV keelte ühesus. DEF: Kontekstivabaks grammatikaks (KV) nimetatakse nelikut G = (N,Σ,P,S), kus N on mitteterminaalide tähestik, Σ on terminaalide tähestik (neil pole ühisosa), P ⊆ N×(N∪Σ)* on produktsioonide lõplik hulk, S on lähtesümbol (mitteterminaal). DEF: KV grammatikaga G = (N,Σ,P,S) genereeritav keel on sõnede hulk L(G)={ x | S * x ning x ∈Σ* } (iga x, mis kuulub terminaalide tähestikku ja on produtseeritav lähtesümbolist). DEF: Sõnede hulk L on KV keel, kui leidub KV grammatika G, nii et L=L(G).
annaabi.ee 
