"kontekstivabaks" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

vt punkt 15 kui α-st saab β ühe tuletusega: vahetult tuletatav α β 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).