"tuletussammuga" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

Tõepoolest: kui z = az′, siis xaz′ ∈ L yaz′ ∈ L iga z′ ∈ Σ* korral. Lisame automaati sümboliga a märgendatud ülemineku Ci → Cj . Konstrueeritud automaat aktsepteerib keelt L ja on lõplik. Järelikult on keel L regulaarne. 7 Fraasisturktuuri grammatikad ja keeled. 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