Produktsioonid

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

Kui me tahame loomulikus keeles defineerida mõistet (struktuuri) "lause", kasutame me abimõisteid "alus", "öeldis", "sihitis" jne. Ka eelmises peatükis vaadeldud loomuliku- ja programmeerimiskeele kirjeldused kasutasid selliseid abimõisteid; neid nimetatakse mitteterminalideks.

Näide 1. Oletame, et me tahame kirjeldada tähestikus T = {0,1} mõistet Paaris_kahendarv, s.t. sümbolitest 0,1 koostatud jadasid, mille lõpus on 0. Loomulik on algul defineerida abimõiste Kahendarv, mis on suvaline sümbolitest 0,1 koostatud jada:

Kahendarv 0 (s.t. kahendarv on sümbol 0)
Kahendarv 1 (s.t. kahendarv on sümbol 1)
Kahendarv Kahendarv 0 (s.t. juba genereeritud kahendarvule kirjutatakse lõppu 0 )
Kahendarv Kahendarv 1 (s.t. juba genereeritud kahendarvule kirjutatakse lõppu 1 )

Paaris kahendarv on Kahendarv, mille lõpus on 0:

Paaris_kahendarv Kahendarv 0

Eespoolesitatud definitsiooniridu Kahendarv 0, Kahendarv 1 jne nimetatakse produktsioonideks. Esituse kompaktsemaks muutmiseks esitatakse sama vasaku poolega, s.t. sama mitteterminali defineerivad produktsioonid tavaliselt nii:

Kahendarv 0 | 1 | Kahendarv 0| Kahendarv 1

Näide 2. Täisarv (tähistame lühemalt: Int) on sümbolitest 0,1,2,3,4,5,6,7,8,9 koostatud jada, s.t. see on kas üks number või (lühem) täisarv, mille lõppu on kirjutatud veel üks number, seega täisarvu defineerimisel on otstarbekas kasutada abimõistet Number:

Number 0|1|2|3|4|5|6|7|8|9
Int Number | Int Number

Reaalarv (Real) koosneb kahest täisarvust (reaalarvu täis- ja murdosa), mille vahel on murdosa eraldaja (programmeerimiskeeltes tavaliselt '.'):

Real Int . Int

s.t. reaalarvu defineerimisel on kasulik abimõiste (mitteterminal) Int.

Produktsioonisüsteemid esinevad mitte ainult arvuti- ja keeleteaduses, nende abil on väga loomulik kirjeldada paljusid elus- ja eluta looduses toimuvaid protsesse ja nähtusi. Näiteks rakkude paljunemine (kasv organismis) sarnaneb produktsiooniga: rakk pooldub ja selle asemele tekib kaks (või enam) rakku. Hollandi bioloog Aristid Lindenmayer arendas eluslooduse vormide kirjeldamiseks formaalse süsteemi, mis põhineb produkstioonide kasutamisel.

Taimede arengut võib kirjeldada produktsioonidega, milles kasutatakse mitteterminale
haar(n) - arengutasemel n oleva oksahaara kasvatamine (kui n=0, siis mitte midagi) ja
vars(n) - sirge oks, mille pikkus kahaneb n kahanedes - vähem arengutsükleid läbinud (noorem) oks on lühem.

Mingi taime oksa arengut võib kirjeldada näiteks produktsiooniga

haar(n) vars(n) [+ haar(n-1)] vars(n-1) [- haar(n-1)] [+ haar(n-1)]

kus [+ haar(n-1)], [- haar(n-1)] tähendab mingi nurga võrra vastavalt päripäeva ja vastupäeva pööratud madalama arengutasemega okste ilmumist. Kui nurk = 200 ja n=7, saame selle produktsiooni abil esimese kõrvaloleval joonisel kujutatud taimeoksa, sest ülalesitatud produktsiooni võiks "sõnadega seletada" nii (vt. kõrvalolevat esimest joonist):
otse, haru paremale, otse
(aga noorem, s.t. lühem oks), lõpuks harud paremale ja vasakule.

Produktsioon

haar(n) vars(n) [- haar(n-1)] [+ haar(n-1)]

genereerib nurk = 260 ja n=7 korral teise oksakese: otse, seejärel harud paremale ja vasakule.

Produktsioonide abil on lihtne kirjeldada ka paljusid looduses esinevaid fraktaalseid kõveraid ja pindu, s.t. kõveraid ja pindu, mille alamlõigud/osad sarnanevad kogu kõveraga - kui palju me ka ka ei suurendaks, suurenduses näeme (peaaegu täpselt) samasugust pilti; sellised jooned on näiteks rannajoon ja silmapiir.

Näiteks silmapiirijoone tekkimist võib kirjeldada produktsiooniga

silmapiir(n) silmapiir(n-1) silmapiir(n-1)

kus silmapiir(n-1) silmapiir(n-1) tähendab kahe "madalamat järku" silmapiirijoone järjest joonistamist ja silmapiir(0) saadakse, kui sirglõigu keskpunkti liigutatakse juhuslike parandustegurite dx, dy võrra; kõvera samm-sammulist arengut n=0,1,2,3 jaoks illustreerib kõrvalolev joonis.

Samasugust põhimõtet kasutavad digitaalseid maastikke genereerivad programmid (Bruce3D): alatakse tasapinnalise nelinurgaga; arengusamm (produktsioon) seisneb nelinurga keskpunkti nihutamist (kolmemõõtmelises ruumis) juhuslike paranduste dx, dy, dz võrra ja seejärel rakendatakse nelinurga igale veerandile sama algoritmi.

Käekirja kirjeldamiseks ja analüüsiks on edukalt produktsioonisüsteemi, mis kombineerib nelja joonekese kombineerimisel, s.t. neist "sõnade" moodustamisel. Joonekesed on graafilise tähestiku "tähed", kuid erinevalt tavalisest (trükitud) teskti moodustatamisest võib neid "sõnas" sobiva nurga võrra keerata ja suurendada/vähendada - nii nagu teevad ka inimesed käsitsi kirjutades.

Geomeetriliste kujundite korral on sageli arusaadavam kujutada kogu produkstioon graafiliselt. Kui produktsioon on (näiteks) selline:

ja derivatsioon algab kolmnurgast (produktsioone sirglõikudele rakendades kohandatakse vasaku ja parema poole pikkused asendatava lõigu pikkusega), saame paari derivatsioonisammu järel lumehelbekese.
Ülesandeid:
1. Koosta produktsioonisüsteem, mis kirjeldab kõik sümbolitest 0,1 koostatud jadad, mille pikkus on paarisarv.
2. Koosta produktsioonisüsteem, mis genereerib kõik sümbolitest 0,1 koostatud jadad, milles on samapalju 0-e ja 1-i ja mis algavad 1-ga, s.t. hulga
{w | w {0,1}*, w = 1w', |w|0 = |w|1 }.
3. Milline peaks olema produktsioonisüsteem "loomuliku" maakaardi genereerimiseks (näiteks arvutimängu jaoks), mis koosneks erinevatest maakondadest koos hierarhilise linnade-asulate-külade süsteemiga: kogu kaardil on üks pealinn (selle nimi ei pea olema Tallinn ), igal maakonnal on samuti üks keskus ja paar madalama taseme keskust (asula-küla). Erinevalt ülalkirjeldatud mägimaastiku ja silmapiiri genereerimisest ei saa siin genereerimisega minna "sügavuti" (s.t. genereerida maakonnale alam-maakondi), vaid peab minema "laiuti" - olemasolevate maakondade juurde (vahele) tekitatakse uusi; selle juures võivad juba loodud maakondade piirid muutuda, kuid neid ei või jagada mitmeks osaks (Saaremaa ei või jätkuda Peipsi ääres; erandiks on Venemaa, mis "tekib uuesti" Kaliningradi ümber).
4. Milliste reeglite järgi kasvavad kõrvalolevad puud?
5. Mida (millise hulga) genereerib järgnev produktsioonisüsteem (algus: R):

R N I K
I N 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 I | 1 I | 2 I | 3 I | 4 I | 5 I | 6 I | 7 I | 8 I | 9 I
K K , I

6. Mida (millise hulga) genereerib järgnev produktsioonisüsteem (algus: R):

R N R 0 | R 1 | R 2 | R 3 | R 4 | R 5 | R 6 | R 7 | R 8 | R 9 | I , 0 | I , 1 | I , 2 | I , 3 | I , 4 | I , 5 | I , 6 | I , 7 | I , 8 | I , 9
I N 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 I | I 1 | I 2 | I 3 | I 4 | I 5 | I 6 | I 7 | I 8 | I 9

Küsimused, probleemid: ©2004 Jaak Henno