"fraasisturktuuri" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

Olgu lõppolek Ck ekvivalentsiklass, mis ühtib keelega L ehk kui x ∈ Ck ja x ∈ L, siis kui y ∈ Ck y ∈ L. Kui x ∈ Ci ja y ∈ Ci, st xz ∈ L yz ∈ L, siis kuuluvad sõned xa ja ya ka ühte klassi Cj. 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.