Produktsioonisüsteem

Lõplike keelte (keel = märgijadade hulk!) esitamiseks võib alati loetleda kõik keelde kuuluvad sõnad. Lõpmatute keelte esitamiseks tuleb kasutada mingit rekursiivset mehhanismi, mis

kirjeldab mingid keelde kuuluvad jadad (lõpliku arvu);
kirjeldab, kuidas keelde kuuluvate jadade (s.t. selliste jadade, mille keelde kuulumine on juba määratud) ja abi- ehk üldmõistete abil saada sõnade alamlõike asendades uusi keelde kuuluvaid jadasid

Sellised asendusreeglid e. produktsioonid on sõnapaarid
v nool

v'
Produktsioon p: v nool

v' genereerib sõnast w sõna w', kui sõnu w, w' saab esitada kujul w = uvz, w' = uv'z (s.t. sõnad v, v' on vastavalt sõnade w, w' alamsõnad, u ja v on suvalised sõnad); öeldakse ka, et w' on saadud sõnast w produktsiooni p rakendamisega ja tähistatakse w

_p w'.
Noole

asemel kasutatakse mõnikord ka muid sümboleid, näiteks programmeerimiskeele süntaksi kirjeldamisel (nn Bacus-Nauri valemites) kasutatakse sageli sümbolit ::=

Produktsioonisüsteem on produktsioonide hulk (lõplik). Produktsioonisüsteem P genereerib sõnast w sõna w', kui leidub derivatsioon

w _p1 w₁ _p2 w₂ ... _pn w_n = w'

kus p1, p2,..., pn P

või lühemalt w *_P w'

Konkreetset produktsiooni või produktsioonisüsteemi tähistav alaindeks jäetakse sümbolites _p, _P sageli ära, kui kontekstist on arusaadav, millist produktsiooni või produktsioonisüsteemi mõeldakse, s.t. derivatsiooni tähistatakse lihtsalt w w₁ w₂ ... w_n = w' ehk lühemalt w * w'

Näide. Produktsioonisüsteem {a nool aba, ab nool ba} genereerib sõnast ab kõikvõimalikus sõnad, kus on sama arv a-sid ja b-sid, s.t. sõnade hulga {w | |w|_a = |w|_b}

Ülesandeid:

1. Kirjelda genereerimissüsteemid, mis

genereerib kõigi sõnade hulga tähestikus {0,1}, mille pikkus on paarisarv, s.t. hulga {w, | |w| = 0 (mod 2)};

genereerib kõigi sõnade hulga tähestikus {0,1}, milles on ühepalju 0-e ja 1-i ja mis algavad 1-ga, s.t. hulga
{w | w

{0,1}*, w = 1w', |w'|₀ = |w'|₁ - 1 }

Küsimused, probleemid:

jaak@cc.ttu.ee

Tagasi loengute sisukorra juurde